I did the trip Timbuktu to Touadenni and back again in Dec 2005. I went with a good guide from Timbuktu. There are some fairly tricky passes. I do not have the gps points. My sat nav was stolen when I got back to Europe. I was in a fully kitted out HD J80. The trip there and back took six days. I used 350L of fuel for the return trip. I had to buy extra fuel in Toaudenni from barrels to make the return journey.
I would not do this route unless you have desert experience or a good guide.
I had not done any desert trips before this one and found it fairly tough. If you are in Timbuktu and just want a shorter trip into the desert you could try Timbuktu to Aruan, this is about half the way on the road to Tauodenni. I thought Aruan was beautiful. Its just a few houses in a dune setting. There was no fuel for sale when I was there. People were friendly.
I do not know about changes in security since Dec 2005. Not many overlanders make it to Toudenni from Timbuktu, it an active caravan route but you could not use the caravan route to follow, a few trucks use the route to carry salt from Toadenni to Timbuktu. I many places there is no piste to follow because so few vehicles go this way and in places where the sand is hard and flat you just chose your own direction.
My guides advised against going East of Taudenni at the time I travelled, for security reasons.
I don't often look at this forum. If anyone wants contact details for the guide it is best to email me email@example.com