Just got back from a few weeks in egypt, and did Cairo-Luxor-Edfu-Marsa Alam-Suez-St. Catherines-Suez-Cairo with no convoys except a "private escort" for the first 20km on the desert road between Edfu and Marsa Alam.
Cairo down to about 20km north of Luxor was surprisingly straight-forward - we were stopped at several checkpoints but talked our way through pretty easily. (We took the road directly on the west coast of the nile, going through El Minya, Mallawi, Asyut, Sohag and Qena. Had lunch in El Minya, where they seemed quite surprised to see foreigners - but, ironically, that province/department had the best signage in english of any.) Several times the police tried to send an officer with us, but our car was full, so they just scratched their heads and let us through. The road has lots of speed bumps until you cross the nile at Nag Hammadi, so it took us quite a bit longer than we were told to expect.
The police in Qena were quite concerned about letting us continue, but by that point it was pretty late (see above re time estimate!), so they didn't have much choice (having sleeping kids in the back probably helped).
The worst checkpoints were right before Luxor, and leaving Luxor to head to Edfu (we took the east bank road). Leaving Luxor the convoys are at 7, 11 and 3, so we timed it to leave Luxor at 8 and talked our way through (again, kids in the back probably helped). They held us at the checkpoint for about 15 minutes, and told us we had to go back to Luxor for the 11am convoy, but eventually let us through after we promised to "sign a paper" to relieve them of liability (which they didn't actually have us do).
Out of Edfu we took the road across the desert to Marsa Alam, and the police sent an escort for the first 20km (we had to wait about 15 minutes for the car to come out from Edfu to join us), but at the next checkpoint just waved us on. It seemed to help that we obeyed the speed limit for that 20km (the police car hung way back). Each checkpoint after that just looked at our papers and waved us on. Note that the Edfu-Marsa Alam road is brand new (just finished 3 months ago, we were told), and they've just finished building a HUGE rest area/cafe half way along (with 60 restroom stalls!), so within 6 months or so you should probably expect that there will be the equivalent of the 70 bus Hurghada/Luxor convoy going on the Marsa Alam/Edfu road.
No problems at all on the coastal road from Marsa Alam to Suez, or from Suez over to St Catherine's (though the checkpoint at St Catherines couldn't figure out why we were driving west instead of going with everyone else over to Nuweiba, and insisted on looking at everyone's passports and finding all the visas). Also no problems at all between Suez and Cairo.
So, approx 3000 kms with only 20 km of escort. Maybe the situation is improving - and good luck!