The Middle East was mostly Christian for centuries after the conquest.
If the arm of Islam on the West marched through to France and won, while at the same time a mixture of poor policies, overtaxation, and civil wars led to a Byzantine resurgence, then you effectively accomplish this scenario if Islam an remain a dominant force without the Middle East.
The greatest issue with getting this situation is that Islam's holiest sites are in Arabia. Not impossible to have a Christian power rule over the area while Europe turns Islamic, but the temptation of bringing the holy sites under Islamic rule would be pretty immense.
For the most part, Christians did not give serious consideration towards reconquering their holy sites until the Crusades whipped up a frenzy of fervor that rather rapidly petered out. The only areas where there were concentrated efforts at reconquest was the reconquista, and any serious study of that shows a healthy mixture of pragmatism and opportunism in leadership positions. Also, rather funnily enough, the crusading spirit of the reconquista was turned towards the New World rather than towards continuing to reclaim holy sites or challenge Islam to any considerable sustained degree until one could bring up hegemonic concerns regarding the Ottomans and the Spanish EmpireThis. And the holy sites are pretty problematic to reach, let alone conquer.
OTOH, very important Christian holy sites have been under Muslim rule for centuries, attempts to conquer them largely failed in the long term, and that did not ever impede pilgrimage.
It's much harder to do something similar in Mecca, but you see the template.
I think keeping the Byzantines in the Eastern Mediterranean is not as hard as one might think. Migrations into Europe didn't stop with the Germans, and the Byzantines had been effectively battling them until Anatolia and the Balkans had made Greeks and Greek speakers minorities in their own homelands. Those migrations were sparked by events that a POD with the Caliphate breaking apart and Rome resurging would not necessarily break. There will be significant conflicts along the Persian border, and the northern border. While I'm not saying they couldn't try to pull another Justinian, in fact its likely someone down the line would, there's nothing that says their tampering might now actually make local Christian leaders side with the Islamic forces in a way similar to how local Roman elites sided with Germanic leaders when the Romans tried to reclaim Rome.Yeah, this sounds the most plausible. Islam spreading further into Europe can decentralize and weaken the Caliphate earlier, permitting TTL equivalent of the Macedonian resurgence happen faster, allowing Romans to cut the Islamic world in half by seizing Egypt and the Levant. Nestorian Turks/Mongols can finish the job in Mesopotamia and Persia. Persecutions, discriminatory taxation, and forced evictions ought accelerate de-Islamification, with refugees from Egypt boosting Islamic population of Europe. Meanwhile, both Empires try to control Arabia and gradually convert the people there.
TTL ERE would have to be engaged heavily in the East to not turn back to help Europe though, at least Sicily and Southern Italy. One possibility might be for them to go to a full Alexander mode trying to restore the Argead borders instead of a Mediterranean focus. Another might be a struggle to death with the alt. Turks/Mongols that will see them ignore the West. A massive theological split (Iconoclasm lasting?) might make reconquest of Latin lands less appealing.
But yeah, probably not ASB-just very very hard to achieve. I am trying to do something similar in my TL, but Europe will not be explicitly Islamic there (only a large minority outside Roman lands and Scandinavia, though Islam would heavily influence the various Christian sects that dominate Europe.)
For the most part, Christians did not give serious consideration towards reconquering their holy sites until the Crusades whipped up a frenzy of fervor that rather rapidly petered out. The only areas where there were concentrated efforts at reconquest was the reconquista, and any serious study of that shows a healthy mixture of pragmatism and opportunism in leadership positions. Also, rather funnily enough, the crusading spirit of the reconquista was turned towards the New World rather than towards continuing to reclaim holy sites or challenge Islam to any considerable sustained degree until one could bring up hegemonic concerns regarding the Ottomans and the Spanish Empire