Let me think about the immediate consequences:
Spain would become a base for the Visigoths for some time, and probably be attacked by the Byzantines if they could tighten their grip on North Africa, and most probably by the Franks who were catholic (as opposed to Visigoth Arian Christianity).
North Africa would be a Byzantine province, as before.
Byzantines would stay. Due to its relative modernity in comparison with the other European Kingdoms and without the permanent threat of a great Jihad on its southern borders, they could well survive and become the predominant Christian power.
The Persians would stay Zoroastrians. If they would stay it in the long run depends as well on their success against the Byzantines.
Arabs would become either Christians or Jews, and probably develop a special sort of those religions which would be very similar to Islam (say what you want, but Islam is a product of Arab pre-Islamic culture, and they wouldn't suddenly become wholly different people just by adopting another religion). In fact, I fail to see many differences if they would take the Old Testament in literal sense as many are taking the Quran.
On the other hand, they could fall under the Byzantine and Persian sphere of influence and adopt their cultural traits.
The crusades are another thing. It is quite en vogue to describe it as an act of purely Western agression, but one should not forget that they were predated by a long period of Arab conquest and, finally, the taking of Jerusalem from the Greeks, who might have been Orthodox, but were still Christian. However, a special sort of Crusade, directed against Orthodoxy, could evolve, but this should involve a serious deterioration between the two faiths.
About Asia, ask someone who is more competent than me. Which is not that hard.
