I think fatimites, Great Moravia, seljucids and almoravids should be at game (damn CA that limits number of factions).

Almoravids are quite different, mainly in troops, to Al-Andalus faction. I accept present them at un-locked new units if there is not other solution, but definitely Al Andalus and almoravids are not the same.