There used to be a stash of half used Michelin deserts left over from the Dakar rally available in the Atar marketplace.
With a bit of searching, I managed to buy two decent (at least 70% tread) 140-80-18s in Jan 07. Now that the rally no longer ventures into Africa, the chance of these still being available is probably limited, but there might be a few left overs from the Africa race, Heroes / Legends etc that might make their way to the market. Since most of the rallies stop overnight near Atar, this is probably a better option than Nouakchott. Otherwise Tidjani at Garage Sahara in Nouakchott might be able to point you in the right direction. His details are posted in the Africa workshop section.
Ask around and let us know how you get on.