The Endless Sands are a spacially expanded area located 1-E-15N-4.
From the outside, the sands only stretch a few dozen kilometers, but once entered, the extent of the Sands are truly endless.
There are a few cities scattered amongst the Sands, most of them are simply called Oasis, This can become confusing, yet a simple answer presents itself. Most of these cities, are in fact the same city. The cities are mirrored reflections of each other, sometimes literally, sometimes figuratively, and sometimes it's a future or past version of the city. Rarely is actual time travel possible, but rumors persist.
(as a note, don't do true time travel unless you really want the headache)
Traveling the Sands is only possible at night, and then only with the correct skills in astronomy, with an astrolabe. If the navigation rolls succeeds, it only takes 1d6 nights travel to reach any destination in the Sands, even the exit.
Maps of the Sands are always in the form of star charts. These charts make no god-damn sense outside the Sands.
Dangers of the Sands;
The Day-Time Heat. This can be deadly without shelter and water.
Sandstorms. These roll through, day or night, and basically ruin your day. Characters will want to be bunkered down in tents before one of these hits them. (weather/survival/ sense skills should be able to give 1d6 hours advance warning)
Sandstorms can move a camped caravan, and there are some planned routes through the sands that require such a sandstorm. Tales persist of ancient tombs, and great treasures to be found on such routes. The reality is that great treasure comes with great danger.
Sandstorms can also drop off monsters or such at GM discretion.
Jinn, Genies, and spirits of the sands, or whatever name you give them. They're everything from small helper/prankster spirits to beings of almost Godlike power, limited only to the Sands. Some will cut deals, some will grant wishes, and none of them can be trusted. They cannot leave the Sands.
Culture. I'm borrowing heavily from the ideas of Arabian Nights here, There would be a distrust for sunlight, because navigation is only possible by starlight, so idioms like "only starlight tells the truth" would show up. or possibly a "Are you telling me by daylight?" for "are you lying to me?". If you distrust a person, you might even say something like "Tell me that on the rock" because "the rock" is the ground outside the Sands. and Jinn cannot leave the Sands, no matter their power level.
As a thought for clarifying things. The shifting caves are via earthquakes, cave ins, and tunnels that collapse into others.
This is much less likely to happen to caravan routes, mostly for narrative reasons.
Infinite ever shifting caves are incredibly useful to the story, being constantly lost is not. Not unless that is the story, and it should be the players who decide that.
If only through a botched roll.