I prefer Muwahid also, for morale reasons. Saracen tend to rout sooner than the Muwahid, but they should slaughter Saharan calvary under normal circumstances. Were the Saracens facing the calvary, and in Hold position? High morale, high valour Saharan calvary can rout Saracens if they hit them in the flank or the rear.

As the Egyptian faction, the Muwahid were the backbone of my armies. I won a Normal/Domination campaign game fairly quickly with them.