One year ago we made a 5 months trip from Libya via Sudan, Ethiopia, Djibouti to Yemen, Oman, UAE SA, Jordan, Syria, etc. Some of the visa needed we had to collect on our way.From Djibouti we took a local Dhau going to Mokkah (Yemen) as there was no RoRo traffic from there to Jordan, Saudi or Yemen. Price was 500 USD for the Captain and some more 500 USD for all kinds of additional costs. After some waiting it might be possible to find a container vessel heading to Europe. To my best knowledge, there are Dhaus going from Asab (Eritrea) to Mokkah or Hodeida, but certainly no ferry or container ship. There is, however, an official regular ferry from Port Sudan to Djeddah. You may get the Saudi visa in Khartoum after some waiting, provided you have the Jordan visa in your passport and a letter of recommendation issued by your embassy there. In Addis you may get the Djibouti visa within 24 hours and most likely the Yemen visa, too. In Sanaa you can get the Saudi transit visa (with recommendation letter) and the Oman visa.
As for the Syrian visa, I want to point out that it is nearly impossible to get it in Amman, Jordan. They issue it to residents only! You have to ask your embassy to intervene at the Syrian embassy. We did it and we got a 2 days transit visa finally! In order to enter Syria, a carnet is required and you have to pay 100 USD diesel tax a week if you happen to drive a diesel powered car.
More info you will find on my website which is still under construction (
http://www.members.aon.at/sahara)
Wish you good luck, Reinhart