The New Road
The road is not really new I travelled along it in Jan 2006. There is at least one good station. It is a boringish road, but it does make it faster with four children. Just watch out for shfting sand dunes, they can make it a bit lumpt at 80kmh.
Also be very careful coming out of Layounne - way too many traffic cops.
Fuel is not really a problem in Mauritania any longer. However, I seem to recollect that Western Sahara was much cheaper.
P.S. Ages since posted on here, I have just bought a Land Cruiser though and cannot wait to get back to the Sahara - LJ78 - it is gorgoeus.
Much better than a Land Rover (I say that after ten years of Land Rovers)
I came, I saw. I ran for it.