It would be interesting if the ERE had collapsed during the 6th century and in its place several national kingdoms had arisen. For example, Justinian is killed in the Nika Riots, a grand civil war begins in the ERE, with the monophysitic parts of the Empire seeking independence from Constantinople. Around 570 to 580's in the place of the old empire we have four major states, ruled by former Roman generals:
a) Kingdom of Romans and Egyptians, Monophysitic, Coptic-speaking, covering the african parts of the empire.
b) Kingdom of Romans and Syrians, Monophysitic (Jacobite) with significant Orthodox (Melkite) and Nestorian minorities, Syriac-speaking with Greek-speaking Minorities, covering the Levant and having Antioch as its capital.
c) Kingdom of Romans and Armenians, Monophysitic (Gregorian) with significant Orthodox minorities, Armenian-speaking with Greek-speaking Minorities, covering all lands east of Halys River (Kızılırmak in Turkish), such as the regions of Pontus, Cilicia, Capadocia and Armenia.
d) Kingdom of Romans and Greeks, Orthodox, Greek-speaking, the remnants of the old Empire, Western Anatolia and the Balkans.
The three first kingdoms would have very good relations due to their common faith. Actually, Syria and Armenia would face together the Sassanid Empire and would conquer Mesopotamia during the 590's, puting under their shield the local christian, syriac-speaking populations.
Also, Egypt and Syria would face effectively the spread of Arabians and Islamists, because they did not have any internal problems or riots. Islam remains in arabic peninsula, in some parts of the African Horn and in southern parts of the Sassanid Empire, which is ver unstable.
The Kingdom of Romans and Greeks (the name Greeks was added during the 8th century) stays focused in the Balkans and managed to defend better their territories against Avar and Slavic invasions. They manage to keep for themselves all the lands south of Danube River. As the years pass, this state acquires a more Greek-national character.
Slavs build many principalties in present-day Romania and the Panonian Plains, untill the Magyars come. Finally the Magyar and Slavic states develop strong ties with the Greek Kingdom.
So, we talk about a TL with no ERE, many national states in its place, very strong Monophysitic Christianty and much weeker Islam. Also, it's very possible that there is no Pentarchy of Patriarchs but only a Diarchy of the Patriarch of the West (the Pope) and the Patriarch of the East (the Patriarch of Constantinople). A stronger Eastern Patriarchate with stucture similar of this of the western church (with Exarchs instead of Cardinals) may mean that soon enough balance between them is found or an earlier Schism happens. Also, no Crusades of course. But HRE is still possible.