who are those folk?
From the difficulty and see-saw battling over Anatolia you seem to predict for this scenario, perhaps, in an example of parallel history, Anatolia is only firmly Islamized after Oghuz Turks migrate there a couple centuries later. The Caliphates will likely still be importing Turks, many Turks will probably still be coming to the Mideast as free men. There might not be as much prospect of loot to attract Turkic Ghazis, but as a scene of constant fighting, it's a place for them to go to work.
So maybe by the 1100s we have an Anatolia that is mainly Arabophone in the south and Turcophone in the north, but with a heavy presence of non-Turcophone minorities.
Given probable limits of Caliphate expansion beyond Thrace, and the requirement to politically submit to the Caliph when converting in the first centuries of Islam, when would the prospect of Balkan and Russian and other east European chiefdoms/kingdoms/khanates converting to Islam from the top arise?
In other words, the spread of Islam in southeast Europe would realistically be quite limited by say 800 CE. But by 1000 CE or 1100 CE, how much of Europe might be Muslim?
Well the Turks would certainly not be transported unless certain policies and ideas spread in the Islamic world. The Umayyad for instance, would never due to their particular political affiliation, would not be able to hire and use Turkic Mamluk warriors at the same efficiency as the Abbasid. This thus, lessens the presence of Islam amongst the Turks by massive amounts. The main reason for Islamization of the Turkic peoples under various commanders arriving in the varied Muslim regions, was the Mamluk system which converted Turks to Muslim, who then rose through the ranks rapidly. Within this, Turks were inspired to convert to Islam and the comfort of many of their comrades being Muslim, allowed them to convert fairly easily.
Umayyad are also based from the city of Damascus in Syria and to a great degree, the Mediterranean coastline. It's later counterpart, the Abbasid, were from Baghdad and thus, focused towards the east, which happens to be the source of Turks. Umayyad power is thus not conducive geopolitically toward relations with the Turks. Even in the 740s, the Umayyad had yet to fully gain firm control over Khursan, Afghanistan and Ferghana. The lands east of Iran were especially turbulent and essentially, there was no Umayyad control. Umayyad powers further were humiliated multiple times against the Ferghani and most famously, the Peacock army was defeated resoundingly by the Zunbil in southern Afghanistan. This cut the path toward India for the most part and created a non Muslim wall around the Hindu Kush. The Abbasid arose from this turbulence in the east and gathered a significant force to defeat the Umayyad. However, this may not occur as otl.
Without the Abbasid revolution and the following coup, the situation in the East likely remains similar with only minor improvements. Umayyad success in Europe thus may have the effect of furthering this chaos to the point that other powers may gain significantly. However, who or what power this would be, I am not sure. The Tang are the first possibility, itself has the power to bring Ferghana under its influence or at least as some sort of tribute akin to the Tocharian whom the Ferghani were. There is also the eventual conglomerations of Turkic peoples who may have the opportunity they need to take areas such as Kwarezm which are only nominally Umayyad at this point as is areas such as Nisa.
In a more clear sentence, I am not sure the exact situation occurs, in fact, I am sure, in the East and with the Turks if we have the Umayyad remain the hegemonic power of Islam as opposed to the Eastern oriented Abbasid.
Paulicians were a Manichean Christian sect which was somewhat radical in its belief that Christ was the serpent in the garden of Eden. They further, were fierce warriors of zealous quality. In the VIII century, they were persecuted by the Byzantine authorities, leading to them rebelling and joining forces with the Abbasid armies. Rapidly, the Abbasid army and the Paulicians now fully integrated into the Abbasid army on the Byzantine border, conquered much of Anatolia and were some of the most well used troops and people groups used by the Abbasid wars against Byzantium. Paulicians were especially associated with the famous general Umar al-Aqta, one of the most enigmatic characters of Islamic historical fiction. Umar al-Aqta and his diverse force of Arabs and Paulicians were defeated at the famous battle of Lalakoan, which was the beginning of the turning tide between Byzantium and the Abbasid hegemony. Umar al-Aqta was slayed at the battle and the Paulicians were essentially crippled from that point on. They are considered the root of the Albigensians in southern France and Bogomils of the Balkans.