Remember that the fatigue is proportionate to armour, and that the heavy armour units are not going to recover their fatigue, and will lose it even when standing, and that the tired missle troops fire less arrows/bolts per volley when tired. You can use the regular troop types, but, for example, try using those that do not have the armour upgrades. I find that units with armour less than 5 are doing quite well in the desert. I think that the threshold of not recovering fatigue is somewhere around 5 as well. Feudal sgts with the first armour upgrade work well in the desert, as do the missiles with no armour upgrades. Genoese sailors are really cool for that if you have them.