I've just currently finished fighting very strong Egyptian armies in the desert on Hard.

As the English, the key to victory was Longbowmen. Forget cavalry initially except perhaps feudal seargants, the Muslims have billions of camels and all their infantry has spears. Also they tire too quickly in battle and romping around the feild trying to get to the flanks.

I used lightly/medium armoured troops such as lots of high valour FMAA to counter their spear and axe infantry, gallowglasses, and longbowmen to cut up, well, everything, and then when they became available I bought billmen on the field to hold the center line.

I have played plenty and plenty of multiplayer battles against my GF in the desert (she likes Egyptians) and heavy cavalry is certianly not the key for me. Every time I've used them it I end up with many dead horses, and anything wearing heavy armour be it ranged or foot gets tired far too quickly to be effective. Energetic ghazi infantry cut through lines of CMAA in the desert like they are peasants.