WS & Mauri
Spent 7 months this year in WS and along the Mauri coast till Nouakchott. Ws is just great. Mine are an issue although rapidly getting better. Mines are however no issue for pedestrians, as most mines are anti-tank mines. However, be really carefull. You can go to La Guera easily, but will get a visit quickly by +/- friendly Mauri soldiers. Cap Blans is perfectly OK, but hard to get there on foot. From Dakhla to border there is a number of fishing villages, relatively easily accessible even for hitchikers with basic supllies + plenty of yummy fish of course. On top of that remember that every few kilometres there are a few (3+) soldiers (forces auxilliares-something like reservists, or marine royal) making sure nobody takes a ride for the Canaries (unless they pay and the soldiers look away). So you will always have company from mostly really nice and friendly people who feel really lonely. Even here food etc. no problem. You need time of course, lots of it. Some places are really dangerous for swimming due to strong currents, especially the beaches south of Dagmar (last petrol station before border). Others are just fine. A fishing village called Roque Chico 15 km west of Dagmar, (tarmac road) is highly recommendable.
There is a Brit in Dakhla - Colin (ask for him in hotel Regency) who know the area around Dakhla and beyond intimately and might want to give you a ride in his LR.
In short, your plan i easily doable if you have time.
Maybe I pick you up somewhere after jan 2009, have the tea ready .
Lastly, a stupid question - surfing or windsurfin?