[xyzzyz]

William Thesiger in his book recounts that the Bedouins he traveled with could also identify and navigate based on the shape of the dunes too, and they had memory and recognition of various dune landscapes from many, many places.

[goodcanadian]

If I had to guess, I would suppose that they are not recognising specific dunes (which would be constantly changing), but patterns in the dunes caused by prevailing winds. I am sure there is something analogous to the Polynesian voyagers recognising patterns in the waves and currents of the ocean.

[xyzzyz]

Dunes are changing much more slowly than you think. They are huge and heavy, and they can hold shape for decades.