You could also have a scenario where the Muslim empire in the Middle East/Asia falls apart because of a more extensive civil war around the year 750. Again, go with the Tours scenario so that Europe becomes Muslim. Around 750 the Umayyad Caliphate collapses into civil war as IOTL, but neither the Abassids nor any other group succeeds in keeping control. Instead, the ummah descends into anarchy with no reognized leader. Besides the Ummayad and Abassids, there are other contenders who spring up in the chaos. The Shi'ites and Kharijites also rebel. A series of disasters follow.
Central Asia deals the Muslim armies a defeat which causes Islam to collapse in that region. Either the native Turks win, or the Chinese intervene and win in a reverse Battle of Talas (historically in 751).
In Anatolia, a revived Byzantium under Constantine V (ruled 741 to 775) is more successful than IOTL as there is less united opposition. He restores Byzantine authority throughout Anatolia, Syria, and Palestine. He or his successors use this as the basis to later reconquer Egypt and even Mesopotamia. Georgia and Armenia are restored by local rebellions.
With the richest provinces now in the hands of their enemies, Muslim power collapses in the Middle East. Native Persians rebel and throw out the Arab invaders. They turn their back on the foreign religion. Instead, the new Persian state adopts Nestorian Christianity to distinguish itself from the Byzantines, the Arabs, and the failed Sassanid Dynasty.
Islam probably survives in the Hedjaz and Arabia given the unprofitability of invading that region, but its power is broken in Asia. However, the Muslims still control northwestern Africa and Spain. A new caliphate emerges in Western Europe that eventually dominates that region. The Byzantines are not able to extend their reach deep into Europe since they are dealing with the Bulgars and a revived Persia. Italy probably becomes a battle ground between the Byzantines and European Muslims. Perhaps with a deal where Rome is kept safe in return for the Byzantines not despoiling Mecca.
The Muslim Conquests were extensive, but not very deep. For a long time, the majority of the population in the Caliphate retained their original religion (especially in the Christian areas). If the Muslims do not retain their military superiority, the local population would be willing to accept whomever moves in next. They are not especially loyal to their Muslim overlords. It took prolonged Muslim rule to turn those socities into majority Muslim lands. I think it wasn't until just before the Crusades that Muslims constituted the majority of many of the former Byzantines provinces. Around 750, there aren't enough roots to truly make the area Muslim except by military occupation.