До Каира нынче не доехали, в новогодние праздники в прошлую поездку самостоятельно ездили из Сафаги в Луксор, Абидос, затем в Луксоре на обратном пути посадили друзей на поезд, они поехали в Каир, а мы вернулись в Сафагу на день рождения подруги. Проблем с ночевками небыло никогда. Нынче, в мае, ездили из Шарма в Иорданию (Акаба-Петра-Шобак-Мадаба-Мертвое море-Джераш и все достопримечательности по пути) нигде не испытывали проблем с ночлегом. Поизучайте путводители, там очень много бюджетных отелей-хостелов.
http://www.hostels.com/ - здесь посмотрите, может что подчерпнете для себя.