After the 8th century AD a Christian Middle East is a possibility, though a remote one. It would probably take the conversion of the Turkic tribes to Christianity, or await the coming of the Mongols, and coincide with a remarkable revival of the Roman Empire, and a long succession of Emperors seeking to follow in Trajan's footsteps with the same passion that their OTL counterparts debated iconography.
A Muslim Europe is unlikely, but not impossible. If Constantinople is somehow taken, and if the Slavs follow Islam, I can see it as possible, though not likely that Christianity could be squeezed out of existence between the vice of Moorish Spain and Muslim-Slavic Russia.
But to switch places I think would be impossible. There really would be no precedent for such an occurrence in all recorded history. Would Darius III have abandoned his heartland to conquer Greece and Macedonia while Alexander was away with his army? And would Alexander be content to conquer the other man's empire in his absence, and decide to consolidate his recent conquests and leave his land of birth to be ruled by his archenemy.
Even if their respective leaders were prepared to accept such an arrangement, the soldiers and colonists who would have to go along with such a plan would not.
Islam could possibly exist with its heart (Mecca) ripped out and the Arabs, who were very much the beating heart of Islam for the first few centuries. But no European fighting force could be sustained in the Middle East without the continued support of Europe. The Arab conquerors were at least fighting for greener pastures.
European conquerors of the Middle East would soon fade in importance like the Greeks who settled the lands of the Diadochi after Alexander. A Christian, European Elite might control the cities, and rule over the country as feudal lords, but that is not a lasting system for bringing about a long-term change of religion in a populace.
