I think some areas shouldnt be conquerable. For example the new city right in the bottom left corner of the Sahara would be about where Burkina Faso is today - on the far side of the Sahara desert. Im pretty sure no armies from europe/the mediteranean could or would marched that far, nor if they did, could an empire be stretched that far, across such hostile terrain. Its one thing to say 'we dont want to eliminate sand wars completely, as the Ptolies/Carthies *could* have declared war on each other', but it is something else to believe it likely that anyone would have tried to send an army south clear across the largest desert in the world...
A no mans land is what the desert should be, as who can own or control such country? Perhaps not impassible in its entirety, but I think scattering patches of impassible terrain (so it becomes like a maze, and takes ages to navigate through) would keep it as an option for launching surprise desert raids, but would make them suitably time-consuming, risky and wasteful, as they would have been in life...