There is great difference between sandy deserts. Sands may be coarse grained or fine grained, there may be areas of compressed sand where only vague marks - if any - are left. In other words, in some areas, it's easy, in others, less so.
Likewise, there is difference between species. Lytorhynchus tracks, as shown above, are very "clean" making it quite conspicuous where the sand is piled up. It may be less conspicuous with other species.
On the whole, I'd say that while losing the trail entirely is a very real concern, discerning the direction of movement - even if it takes a few seconds to figure it out every now and then - very rarely, if ever, is.
I'm sure Jürgen & GJ have more to add on this topic, as they've both tracked more species in more desert habitats than I have.