So, to get the board's opinion; how much of Europe could have become Muslim in the early-to-high middle ages and remained so into the present day?
Islamic Gaul is basically a
big no-no. Arabo-Berbers simply didn't have enough forces or even motivation doing so, while Franks being unified at this point, enough to fight back efficiently as they did IOTL.
At best, you could see a bigger part of Southern Gaul (southern Aquitaine, part of Provence) being taken over temporarily (well it was IOTL, but more than just one year or two ITTL), but it would most likely wouldn't last.
There's a similar issue with Italy, although a more important presence in Late Carolingian era is more plausible. Basically, between Franks and Byzzies, a full-fledged Arabo-Islamic conquest isn't going to be that realistic.
A slower conquest of southern Italy with a weakened Francia and Byzantium, however...
You could see emirates (more or less tied up with Fatimids) being created in Calabria, Puglie, even Campania. But the same problems that plagued Al-Andalus or Sicily (such as lack of manpower, political and strategical isolation) are still going to appear.
It's not going to be easy, but I think it's possible for an earlier Islamic presence in Balkans, that wouldn't get rid of Byzantium per se, but could take on Thracia or even IOTL Bulgaria without being totally impossible.
Eventually a Muslim presence in what is now Southern and Central Russia is doable (but depends on ERE being importantly weakened).
I would think that a Khazar Khanate sticking up to its conversion to Islam, contrary to OTL, could be an interesting religious pole, eventually converting southern slavic emporiae.
Bulgars, on the other hand and if the M-E trade proove mre incitative than Constantinople, could deal (but it would be much harder) with Northern Slavs.
It would fit well with a TL where Constantinople is far less attractive, due to a more warring region.
Basically, the more important obstacle for a greater Arabo-Islamic dominance are Arabo-Islamic structures : still largely tribally and ethnically divided, based on successful raiding for what matters to funding expeditions, with a relative numerical inferiority when it comes to conquered people (and that clearly played a role on religious division with Sh'ia, Kharidjism, etc.). But as long it's "working" you can't simply get rid of them.
I worded that badly. I mean no serious christian empire being left at about 750. So byzantine falls, the frankish empire doesn't form, ect.
It seems a bit convenient to say the truth. Byzantine empire resisted well even in the VIIth century, enough to lives on. Frankish takeover was more or less a given by the VIIth century as well (mostly due to its presence over new trade roads, a wealthy kingdom and common structures)...
I'm not sure having a PoD that conveniently "delete" every big player in the region is that plausible myself.