Ya know, now that I think of it, I've never really had problems with the desert.

The only units that you HAVE to worry about are insanely heavy units and cav like Gothic Seargents, Swiss Armor Pikemen, Gothic Knights, Kataphrakts, and all the other really heavy cav. And the only reason you should really pay attention to them are those insanely cheap camels.

Heavy infantry still outclass or match Muslim units even when tired, they just have so much armor and defense making them able to last even when tired. Just put a good general behind them to counteract fatigue morale penalties so they don't rout. And DO NOT let tired infantry get flanked by cav, that WILL cause an autorout.