Hi Per
Your route is the exact opposite of the one I'm on at the moment. We've spent the last 5 months travelling through Morocco, Mauritania, Senegal, Mali, Niger and Algeria. I'm in Tunisia at the moment and we're heading to Libya when we've got our visas and then on to Egypt, through the Sudan to Ethiopia and heading in a southerly direction, zigzagging our way down the East side of Africa. We're planning to be in Cape Town by Christmas. Wish the trip could be longer, but we're limited by money.
A note on the Libyan visa. I checked at the Libyan embassy in Tunis and it's possible to get a transit visa, which enables you to travel across the top of the country (along the coast). You don't need any invitation or guide commitments for a transit visa. You just need a letter in Arabic, explaining who you are and why you need a transit visa. You submit this to the embassy, along with a copy of your passport. They evaluate your request and if given the OK, issue a transit visa for the cost of 31 Tunisian Dinar. I'm in the process of writing the letter and have to find someone to translate it into Arabic. I'll let you know how I get on with this. Watch this post. It may be possible to do the same thing in Cairo.

Of course, this option means we have to miss out on the Libyan desert, which would be fantastic, but the costs are too high. Algeria worked out cheaper so we decided to spend our money there. We went with Tanezrouft Voyages and we had an amazing trip with him into the Hoggar and then travelling northwards through the desert via Assekrem to In Salah. From In Salah, it was a bit of a trek to the border (1200km in 3 days) and the drive through the Grand Ergs was incredible. We were escorted all the way from Ain Guezzam (Niger border) to Taleb Larbi (Tunisian border). Algeria is the most wonderful country - the scenery is spectacular and the people are very gentle and friendly (careful in El Gorlea though). Mohammed, our guide, read us very well (we were travelling with a guy on a motorbike that had endless battery and wheel problems) and changed our itinerary when he saw the state of the bike on arrival at Ain Guezzam. Our itinerary enabled us to have as much experience of the desert as possible, given our money, time and bike limitations. I've travelled with guides before and I can't recommend Tanezrouft highly enough. It was an awesome trip.
Let me know if you'd like more info on our route so far and our route southwards. It might help you with your planning.
Good luck
Bel