In fact, I already did write something, but forgot. So anyway.
"IC:
Who was Mohammed? Some minor merchant of no significance who went mad and claimed he was visited by some divine being; he died soon after, some claim sniped by a crack penguin team. His only real importance was that he was married on a cousin of Waraqah ibn Nawfal, a Christian ascetic, one of the first Christian missionaries who, too, joined the large crowd of those trying to explain Mecca's fortunes and the nature of Allah - the most controversial aspect of contemporary religious arguments in Hejjaz. Allah, the high god, was accepted by most as the undisputed head of the pantheon worshipped in many parts of Arabia; others, however, who also reffered to him as Rahman and followed Yemenean traditions, believed him to be the only god. Needless to say, the Christians generally had the same idea, thinking Allah to be a manifestation of their own religion.
Since Qusayy the Unifier, who brought together many a nearby Bedouin tribe and led them to the haram - sacred enclave - of Mecca and since the collapse of Himyarites, Lakhmids and Ghassanids, the Quyrash mercantile aristocracy was essentially the only real power left in Hejjaz, as all other towns acknowledged its supremacy. Trade filled their coffers, and the only problem was the disunity of the aristocracy itself; but by the middle of the 8th century, when a very notable event happened or begun to happen anyway, a degree of unity has been attained. Monotheists and polytheists struggled amongst themselves but also within their own groups; Christians, Rahmanists and Jews hardly agreed on the nature of Allah, and the polytheists were just as, if not more, disunited. Waraqah was only one of the Christians who, in late 7th and early 8th centuries especially, fleeing from Byzantine opression (needless to say, the fleeing Christians were Monophysites...), entered Arabia. Long story cut short, in middle 8th century one of the most dominant Quyrash nobles, Abu Mansur, later and better known as Alexander Mansur, converted to Monophisite Christianity. This was the signal the Meccans were waiting for; the signal for the struggle to begin. On Saint Bartholomew's Day (albeit they didn't know it yet) a group of polytheists attacked and lynched a Christian missionary. The massacre begun, despite pleas coming from both sides of the religious debate not to defile the holy city thusly. Monotheists and polytheists fought, but eventually the Christians came out victorious - both against the polytheists and the other monotheists. An important factor was that Abu Mansur called for his private army of Bedouins to assist the Christians; his authority amongst them was great enough for this.
After the Christians took over Mecca, Alexander Mansur with fire and sword proceeded to crusade against the Rahmanists in Yathrib and those Bedouin tribes who opposed him and his faith; most, however, did not, sensing that Alexander won anyway and that all they had to do was to abandon the lesser gods and agree on the newly-decided nature of Allah as the only god, well, that and those funny Christian customs. Having united the Bedouins of Hejjaz, Alexander easily conquered Medina, and thus became the first Christian ruler of Arabia (note, no Yemen, Oman or the eastern half of the Desert; but the rest is pretty much under his control, if often rather nominal due to sparse population in some regions). Arabic Christianity, albeit "Monophysite", apart from that also adopted many old Arabic customs and traditions.
But Alexander's men were restless, and so was he. He needed expansion - and he quickly saw a perfect opportunity. To the north, the staggering giant of the Byzantine Empire, chained by corruption (OOC: in OTL the Arabic conquest of much of the Byzantine Empire gave a good incentive for reforms) and Monophysite rebellions, was on the brink of collapse. Mansur chose the name of Alexander because Alexander/Iksander of whom he often heard was an ancient Greek conqueror who brought down another such empire. Mansur wanted to do that too. So in 777 AD, he, upon hearing of the Monophysite rebel defeat at Antioch, and upon receiving envoys from some of the rebel cities offering him - a fellow Monophysite, after all - the crown of Syria, quickly set out north, being already prepared to invade the Byzantines anyway.
He couldn't have chosen a better time. The Franks were encroaching on the Byzantines in Italy; North Africa and Middle East up to Anatolia were filled with rebellions; in the Balkans, the Bulgars were almost at the gates of Constantinople itself. The Byzantine allies, Persians, only barely found significant forces to commit to help their allies, as the Turks were rising in strenght and daring in Central Asia. Still, Persians and Byzantines scored a pyrrhic victory against the Arabs and the rebels at Yarmuk; but after that, many Byzantine forces had to be recalled. Constantinople was besieged by the Bulgars. Venice declared formal independance. The Frankish Holy Roman Emperor was already in Ravenna - overseeing the construction of his great armade for the conquest of Sicily and the humbling of Venice. Berbers, meanwhile, were celebrating the capture of Carthage.
Arabs failed to completely bring down the Byzantine Empire, but Palestine and Syria were in their hands. Persians were only barely holding them at bay in Mesopatamia. In Egypt, Mansur's Coptic allies rose to power. In 800 AD, the Byzantine Emperor Constantine VI, who presided over the fall of his empire, drunk for the last time the bitter cup - but this one time, not of defeat. Of poison. He drunk it in Ephesus, the capital of the Ephesian Empire, which was the sad remnants of his empire. Byzantine lands in Italy and Sicily - even Venice, which agreed to nominal supremacy of the Frankish Emperor Charlemagne - were forever lost. From Tripoli to the southern Pillar of Hercules, Nusair reigned over a great, if unstable, Berber Empire - the Qaysarate of Magrib (OOC: question. I don't seem to find much about religion there, but it would seem that Monophysites here did not have too great an influence... right? If they didn't, Qaysarate would become "Catholic"). In Egypt, a Coptic Greek kingdom arose, with the capital in Alexandria. Syria and Palestine, joined together with Mansur's previous possessions, were now the Qaysarate of Syria, ruled by Alexander I from the city of Damascus; Syrians themselves, being not too different from the Arabs (I don't mean the Greek Syrians, but the other ones), eventually assimilated them to a certain degree, but even now, the Qaysarate was decisively a Syrian one. And the Bulgar Tsar, Krum, was crowned in Constantinople. Now he was a true Tsar (=Caeser), no?
And the Ephesian rule was not only limited to Anatolia and Armenia. What an ignoble end! But is it truly an end? And Persia, meanwhile, was busy falling to the Turkish attacks; eventually (in twenty years perhaps), the Turks would inherit the entire Sassanid realm, as well as Zoroastrianism and other cultural elements.
And what happened to the other parts of the world?
Well, nothing different in the Americas, oddly enough. British Isles pretty much the same.
All hail the Holy Roman Empire, though. Charles Martel was famed for defeating the upstart Duke Eudes and for the ultimate conquest of Aquitaine. His son, Charles the Great a.k.a. Charlemagne conquered even more. Seeking to unite the Christians (objective later, if unofficially, switched to uniting the Catholics-albeit-back-then-they-were-not-called-that), Charlemagne used dynastic strife in Visgothia to, well, conquer it; wasn't too hard, really, not half as hard as fighting off the Asturian and Basque rebels that sprung up at every occasion. Next to conquer the Lombards, then to conquer cousin Tassilo III... the wars with the Saxons, however, were far less succesful. Entire Frankish armies were occasionally eliminated by the daring Saxon rebel leader, Vitukind. And as Charlemagne, in 772, was again distracted to finish off the Lombards in Italy, he found himself embroiled in the war to end the Byzantine Empire. By then, btw, he was already crowned the Holy Roman Emperor (OOC: note, many historians attributed Charlemagne's decision to partition his empire to the demoralizing influence of Roncesvalles; so for better or worse, no Treaty of Verdun here). He assembled a fleet, conquered Sicily and persuaded Venice to acknowledge, if nothing else, his nominal supremacy; the Venetians agreed, because better relations with HRE meant better trade, and because, well, they basically exchanged after a brief period of complete independance a nominal ruler of a crumbling empire for an even more nominal ruler of a rising one. Good exchange. Charlemagne spent the rest of his life campaigning against Avars and various rebels, but he would never fully conquer the Saxons or the Basques (he would "conquer" the latter, but they always fled to the mountains, waited out and then rebelled again) (OOC: the Frankish Holy Roman Empire is huge, albeit it has no Saxony (which is, like OTL Lithuania until 1251, completely pagan and even more anti-Christian then Lithuania; think Domstolland from Empty America); it is strong, but is also quite hard to keep together the way it is; note, also, that the "Patrimony of St. Peter" is something of an autonomous region within the Holy Roman Empire).
Again, due to Charlemagne's distraction, the defeat of the Avars is even less followed up then in OTL. The local Slavic tribes are beginning to unite around the strongest one; the Moravians. But not much interesting here yet. Further south, the Tsardom of Bulgaria (Orthodox) is ruled from Constantinople and has united pretty much all of the Balkans. Much further north, the Viking Age is beginning...
And needless to say, the Khazars rule supreme north of Byzantine Armenia, with the focus still being on the south of the great empire (albeit, ofcourse, Itil/Volga delta is still under Khazar control; just its not the center of the empire).
The Rahmanists fled for Yemen, where an united monotheist maritime commercial state is beginning to emerge. Mercantile interests meet an increasingly expansionist religion, and all this provides a motive for colonization of East Africa... albeit for now, only some minor coastal settlements on the Horn were founded.
Not much difference in India from the way it was in OTL before Islam. This basically means that Buddhist communities in Sind and points north survive.
Tang China and Tibet are engaged in heavy fighting for the control of Gansu Corridor. The Tang are especially motivated by the fact that their extensive (greater then that of the Han Dynasty!) Central Asian Empire, stretching to Ferghana, recently got increasingly unstable, in spite of the fact that its eastern half is fairly Sinofied.
(More later if you want me to carry this further (to 1000 AD), even though I think its better to start in... 810 - Charlemagne is dead, Alexander died earlier, the Turks finished their conquest of Persia (the negative side to it is that there's not much change elsewhere in the world, albeit its bound to happen with time). Sorry, I guess I got rather carried away from the topic, but I think the Byzantine Empire without the rise of Islam and the reforms that followed stood not much of a chance. Oh, and I welcome constructive criticism especially on the topic of the Rest of the World, on which I am far from sure)"