Thanks Achim for the route advice!

We went to Baaboud in Khartoum to book the ferry but their ferry is out of service right now (maintanance). But they were able to book us on the other ferry (Namma Ferry). We payed US$290 for a Landcruiser and two people (there is only second class).

Hello Ans and Tom,
We got our visa in Khartoum via a visumagent opposite the embassy (Waleed).
We payed a total of 1100 Sudanese Pound for the two visa and for the visumagent. In the end we had to go to the embassy ourself and talk to the people there. There was a very friendly guy (mr. Bandar M. Alnahdi, third secretary) who helped us (he lived in the Netherlands for nine years so that helped because we're Dutch too).

Greetings from Port Sudan!

As others have said, Yemen right now, a real no-go zone.
As interesting a country as it is and as strong as your desire may be it's worth avoiding this one for the time being.

As for KSA, it is illegal to drive a vehicle there as a woman. Although woman occasional do ride quad bikes around but generally in out of town areas as the men don't want their womenfolk bouncing about on a vibrating 2-stroke quad for whatever reason....

You mentioned a woman rode her bike previously? I would guess that she got the bike into the country by someone else or maybe a recovery service and then rode it carefully disguising herself as a woman to wherever she wanted to go and then got it recovered out of the country again. If the police catch you, and they will as people will report it (nothing else to do) and you will end up in jail. Totally not worth it, one day the laws will change to allow women to drive but not for a while yet.

Benka Pulko:

Guinness World Records and Recognition for:
* Longest Female Solo Motorcycle Ride – Distance (111,856 miles)
* Longest Female Solo Motorcycle Ride – Duration (2000 days)
* Documented: First Woman to Ride Across Saudi Arabia
* Documented: First Person to Motorcycle on All Seven Continents

Source: https://www.facebook.com/BenkaPulko/info?tab=page_info

But how did she do it? Even if somehow it was sanctioned she would need a police escort as the chance of being attacked would be enormous.

Other then some positive comments about the locals and some custom-problems I don't know much about her crossing.
There are at least one female rider who got the transit-visa earlier then Benka Pulko but she didn't cross Saudi, she needed it for the ferry to/from Jeddah.

Back in the 70/80s s a single Norwegian female crossed Saudi in a car, I think she also went from Qatar to Yemen and back.

But still I think it's extremely hard to get the visa when traveling on a bike. I have tried several times with pretty good contacts. It's even harder if you are female.