Honestly, I think the desert penalty should apply. The Almoravids and the Almohads based themselves out of the Sous valley, which has been one of Morocco's most fertile areas since time immemorial. It's not like the Sous valley is as inhospitable as the Ahaggar. Ideally, each dynasty should generate with event troops associated with a high decadence and an event chain from the lead up to their takeover, which were always over perceived slights in interpretation of Orthodoxy. Although, I'd imagine that last bit is a VIET kinda thing.
Well, they based their power there but (the Almoravids) after they conquered it from the desert.
The idea of event troops and high decadence for every decadence looks nice, but speaking about desert nomads it is in bright contrast to the concept of decadence (by Ibn Khaldun) which was that the desert tribes actually don't suffer decadence until they move their powerbase and capital to sedentary areas.
Ibn Khaldun's concept of decadence was that sedentary dynasties suffer decadence as opposed to nomadic desert dynasties/tribes who are immune to decadence as long as they stay in the desert. According to Ibn Khaldun normal dynasty declines and after 4 generations it usualy collapses. CK2 concept was a tool to do this, but it still lacks balance. The dynasty, which suffers high decadence is attacked by hordes from the desert with event troops. But as the game was being tweaked, the decadence became too easy to be lowered and therefore it doesn't work at all.
The concept is broken and I think that it should just be this way:
The desert tribes should be immune to conquest from Egypt, Syria or Maghreb etc., they should be relatively weak (economicaly), but strong enough militarily that when the decadence of their sedentary neighbours (Egypt, Maghreb) rises, they should be able to conquer it.
It's not as if them conquering stuff outside the Sahara was ever an issue before I applied the penalty, so the supply limit and tax penalty should be plenty to keep them in check. There's very few holdings in the Sahara, so that alone reduces their levies by a lot, and the holdings nearly only being cities reduces it further.
Sahara is weak, but I actually did some additional research and have found and added few more settlements (circa 20 settlements for all those Saharan provinces, so nothing very balance breaking), because I really think the desert deserves to be martialy stronger.