Hm, so not much hope of building something long term then, huh?
Many of the emirs had to reconquer parts of the territory from rebels upon their ascension. In fact, a prolonged period of revolts actually began in the 850s and it took Abd ar-Rahman III
seventeen years to gain total control. Despite the state more or less existing for 175 years, the period of continuous unity only ran from 929-1009 at the longest.
In my view, the path to a stable Al-Andalus lies in bringing the Andalusi Muslims to power. They formed the vast majority of the populace but they were always pushed down (I hesitate to use the word "oppressed") by the other groups. However they lacked great military power--as a book I read put it, Cordoba wanted to disarm its population (contrast that to Leon-Castile). Also the Umayyads usually used the Arabs to dominate the rest (until Abd ar-Rahman III) so it would take quite a mental leap to use the Andalusi population as a power base even assuming they could be a reliable military asset.
An alternate path may lie in "rolling sixes" for longer in who is in charge as you suggested. An Ottoman like run of great rulers coupled with weak rivals is unlikely, but if you had more strong Caliphs follow AAR-III (it's "time unified" that counts here) the populace might grow to identify with the monarchy more and provide a stabilizing element and more legitimacy for the rulers. Again however I think you need rulers who can manage the ethnic relations and that is a very complicated thing.