Since the whole point of Islam was to bring the faith of Abraham and Jesus back to basics and return it to its roots - as far as Muslim doctrine is concerned, the Qur'an is after all the original, uncorrupted Bible, so to speak - I think that in a world where Muhammad grows under Byzantine rule, easier access to the sources of Orthodox Christianity might mean that alt-Islam might end up becoming part of the wider iconoclastic movement.
This alt-Islam would not become a separate religion, but a distinctly Arabic flavour of Orthodoxy. Depending on who rules in Constantinople, Muhammad could become the man who converted the Arabs to monotheism as practiced by the eastern Romans, and a great general as well.
If he still pronounces something similar to the Qur'an's earliest, tolerant and universalistic verses, he'd end up gaining even more pagan converts, and some figures of Arabic paganism could be recycled as saints, too, with the Kaaba's connection to the earliest prophets being retained.