I think you will struggle to get a visas for Saudi for a man and woman travelling together if you don't have a marriage certificate. I know other travellers have got fake ones to get round this and chances are you would get away with it but does introduce a further level of risk using fake documents.

It appears to be alot easy to get visas for countries in this part of the world in neighbouring countries than trying to sort in Europe. I know other travellers who were repeatedly unsuccessful over several months in trying to arrange in advance but then got visas in 24hours in khartoum for example. The downside to this is that you are already close before you know whether you have it so if you get refused then then its harder to re route. However if you are planning coming through anyway there aren't lots of options, so if you can't get the Saudi visa, its back looking at Egypt.

The other factor is that unless its changed recently, you can't get a Jordan visa in Saudi and I would assume the same for the other countries you could potentially exit into - amongst other factors Saudis normally only issue a 3 day transit visa to cover getting from Jeddah to Jordan so doesn't allow enough time to go anywhere to try and get one and also the Saudis are likely to want to see the next visa before they will issue the transit visa - eg proof that you will be able to exit.