I'll try to stick to the facts about Algeria as we were there last November. We entered Algeria from Tunisia in the south at the Taleb Labri border crossing near Nefta in Tunisia. We had a guide who we organised through Tanzerouft Voyages. We applied for our tourist visas only once we had organised the guide who sent a letter to the consulate to support our visa applications, without this our visas would've been refused. We rode 2up on our Australian registered motorcycle that I own (ie. all paper work is in my name).
1. The land border is closed between Algeria and Morocco.
2. You can enter/exit by road/land border from Tunisia
3. You can enter/exit Algeria by boat from Spain or France. To get to Morocco from Algeria we went via Almeria (Spain).
4. We have written in extensive detail the border crossings and our tour of Algeria in our blog
5. You need a visa to enter Algeria.
6. To get a visa you will need an authorised guide/travel agency to provide a letter to support your application. If you don't do this then don't bother trying for the visa, it will be refused.
7. There have been further travel restrictions on entry to Algeria and especially the south since early Dec '11. http://www.horizonsunlimited.com/hub...-algeria-57191
I haven't made statements about things I don't know like Mali border or travel safety, this is based on our experience from November 2011 and things change so consult with your local Algerian consulate or travel agency to get the latest information.
Algeria was definitely worth the money and effort, it is a great country and the people are incredibly hospitable and generous. I wouldn't hesitate to recommend it but it is expensive because of the need to have a guide at all times.
If you have any specific questions then feel free to PM me.