My $0.02. It's definitely doable. You would go through Europe to Greece, Turkey, Syria, Jordan, ferry to Egypt - all tar.
Then get the ferry from Aswan to Wadi Halfa. This will cost you about 350 GBP, assuming you can get other overlanders to fill the barge up - we paid about 300 quid in early 2006.
The bit from Wadi Halfa to Khartoum will be tricky -either you follow the Nile or the railway line, either road is rather poor. Then it's tar to almost the Ethiopian border, tar through almost all of Ethiopia, then you hit the infamous Moyale-Marsabit road in northern Kenya.
We met a bunch of Italians doing it in a 2CV beach buggy, and a guy heading north who had made it to Egypt in a VW Camper. I've also heard of teams of Smart cars and (new) MINIs doing it, but they have had 4x4 backup.
So I think it's eminently doable, if a bit risky, in a 2WD - pick something like an old Merc with decent ground clearance.
Don't bother with Saudi if you and your partner are not married as you will never get a visa. I also never found any definitive information about the boat from Jeddah to Port Sudan.
PM me if you want any more info.