There are several ferries from Saudi Arabia to Egypt. Many operate only during the Haj season or for Muslim pilgrims, though. This is true for the Jeddah - Safaga and Jeddah - Suez routes.

The exception is the Duba - Safaga connection which is plied by several shipping lines. It seems that KCFMT is the principal operator on this route with two high speed ferries (catamarans) and this seems to be their contacts in Safaga and elsewhere:

KCFMT - Agents

In addition, it might be useful to call the port authority in Safaga (phone: 065 - 325 60 18 or maybe 065 - 45 12 22 or 062 - 25 60 18, website: www.mts.gov.eg ) to find out whether there are any other operators or whether there even exists a ferry from Safaga straight to Jeddah.

I have found out about "Namma Lines". They have three ships, one of which - the "Masarrah" - sails from Safaga to Duba while two others sail from Safaga to Jeddah - but apparently only during Haj season. This is their contact:

http://nesmaholding-eg.com/en/NammaContactUs.aspx

In addition, it seems that El Salam Maritime (two of whose ferries sank in the Red Sea in the past) now operates a catamaran called "Fares al Salam" on the Safaga - Duba route. I do not have any contacts of them but they do have an office or even a headquarters in Cairo.

Yemen:

Yemen is basically still off limits for overlanders! Coming from Oman, it is next to impossible to cross from the East (Hadramout) into the Western part of the country through areas at least partly controlled by Al Qaeda. Only the coast road between Mukalla and Aden might be manageable (but is not advised to take!) with an armoured convoy.

Greetings and safe travels
Achim