A major factor in early Muslim success in conquering the southeastern parts of the Empire was that the locally dominant sects of Christianity were deemed "heretical" in Constantinople; the people there were already under the rule of what amounted to a different religion, as far as oppression and conflict went, under the threat of violence to change their faith or else. The early wave of Arab invaders had leadership politic enough to take advantage of this and offer the locals a deal that looked good compared to their situation under the Emperor; the taxes they had to pay as non-Muslims were not heavy compared to the standard Imperial taxes, and they would be left in peace to remain their brand of Christian. Individuals were free to convert to Islam or not; many did so and lent their talents--in shipbuilding and naval warfare for instance--to the Caliphate. (Others I believe may have been known by Arabic names but remained Christian, and also supported the war against the Empire--I might be wrong about that though).
Taking the Greek heartland of Rum itself would be more difficult because in Anatolia and Greece the dominant (perhaps universal) faith was what the capital city deemed "Orthodox;" the deal would not be as sweet for them and they'd fight and resist even after conquest.
So it comes down to force.
Of course from a Muslim point of view one reason for success was that they were simply correct, conforming to the true commandments of God and guided by true knowledge, and having God's favor. From this point of view it would not be unreasonable to speculate, "What if the ruling dynasty or another rival house with strong claims to the Imperial Purple had seen the light, recognized the error of their Christian beliefs and the truth of Islam, and guided by true knowledge and strengthened by true faith and God's blessing, seized the throne and from it proclaimed their submission to God, the prophetic status of Mohammed, and came to terms with the Caliphate?"
That would raise a thorny question even then--on what grounds could the Roman emperors, with their lineage of authority tracing back to obstinate pagans who among other things had Jesus of Nazareth crucified (Muslims believing Isa was a rightly guided prophet and martyr), persecuted his followers, no doubt thus bearing much responsibility for the muddling and corruption of Isa's true message) and then belatedly adopting and imposing a distorted heresy of the true faith and ruling oppressively under the false banner of the cross--how could these paragons of the corrupt rule of wicked men do other than submit to the Caliph and meekly surrender all of Roman territory to him in trust, while the envoys of the true faith are sent forth from Damascus to fan out and verify that the true message of Mohammed is properly disseminated to the long-benighted Roman lands-these missionaries would of course also be the secular agents of the Caliphate.
Essentially then the Caliphs would expect nothing short of unconditional surrender from the Romans.
It seems obvious enough from the point of view of someone who does not believe Islam is the final word in human spiritual development and the simple truth, that this is hardly reasonable to expect to see happen ever. No one in the Eastern Imperial aristocracy would have any reason to convert to Islam as long as the Empire as a whole is strong enough to stop further losses and hold the invasion at bay, nor would we expect a huge wave of grass-roots popular uprising against the established Church and the Empire that upholds it.
Basically before "Byzantium" can "go Islamic"--beyond the portions of the Empire that did indeed "go Islamic" very quickly and easily, due to their estrangement from the dominant religious setup in Constantinople--it has to be conquered, completely, in detail, with no large bastions holding out. The conquerors might claim to be heirs to the old legitimacy of the Roman Imperium as I gather the Ottoman house did, but they won't retain still less revive the old Roman machinery to implement their will--or insofar as they do, they will reinforce it with parallel hierarchies brought in by themselves, which will check and verify and as necessary override the Imperial channels; the conquered peoples are hardly likely to be trustworthy without such checks.
So--a mighty and total conqueror can claim the laurels of Rome as he wishes, but will surely represent a break with the old Roman order. It wouldn't be "Rum becomes Muslim" so much as "Rum is conquered by Muslims." Or Roman territory can be lost piecemeal and gradually converted to Islam as was the general trend OTL--by the time Constantinople fell, the territory it actually controlled was a pathetic remnant.
Insofar as it is possible then, we might as well say that the Ottomans were in an instance of Byzantium going Islamic. After seven centuries, and by conquest, the only likely path unless one can postulate reasons for the religion that the Empire opposes gaining traction within its own territories; I am drawing a blank as to how that could happen.