How Alexander the Great proves Muhammad wrote the Qur'an

For a long time I thought that Muslims everywhere accepted that the figure of Zul-Qarnain, who appears in Surah 18 of the Qur'an, was Alexander the Great. Certainly the tafsirs and experts agreed; Ibn Hisham was probably the first (c800) but the tafsirs from the 10th century onward all come to the same conclusion. Yusuf Ali, the famous Islamic scholar and translator of the Qur'an studied the episode in depth and wrote this in the appendix to his translation:
"I have not the least doubt that Zul-qarnain is meant to be Alexander the Great, the historic Alexander, and not the legendary Alexander, of whom more presently. My first appointment after graduation was that of lecturer in Greek history. I have studied the details of Alexander's extraordinary personality in Greek historians as well as in modern writers, and have since visited most of the localities connected with his brief but brilliant career."

However, there is body of opinion in the Islamic community which is keen to deny the link. Why should this be?
Firstly, let us examine the salient verses Surah 18.

Verse	Abdullah Yusuf Ali	Pickthall
18:83	They ask thee concerning Zul-qarnain Say, "I will rehearse to you something of his story."	They will ask thee of Dhu'l-Qarneyn. Say: "I shall recite unto you a remembrance of him."
18:84	Verily We established his power on earth, and We gave him the ways and the means to all ends.	Lo! We made him strong in the land and gave him unto every thing a road.
18:85	One (such) way he followed,	And he followed a road
18:86	Until, when he reached the setting of the sun, he found it set in a spring of murky water: near it he found a people: We said: "O Zul-qarnain! (thou hast authority), either to punish them, or to treat them with kindness."	Till, when he reached the setting-place of the sun, he found it setting in a muddy spring, and found a people thereabout. We said: "O Dhu'l-Qarneyn! Either punish or show them kindness."
18:87	He said: "Whoever doth wrong, him shall we punish; then shall he be sent back to his Lord; and He will punish him with a punishment unheard-of (before).	He said: "As for him who doeth wrong, we shall punish him, and then he will be brought back unto his Lord, Who will punish him with awful punishment!"
18:88	"But whoever believes, and works righteousness, he shall have a goodly reward, and easy will be his task as we order it by our command."	"But as for him who believeth and doeth right, good will be his reward, and We shall speak unto him a mild command."
18:89	Then followed he (another) way.	Then he followed a road
18:90	Until, when he came to the rising of the sun, he found it rising on a people for whom We had provided no covering protection against the sun.	Till, when he reached the rising-place of the sun, he found it rising on a people for whom We had appointed no shelter therefrom.
18:91	(He left them) as they were: We completely understood what was before him.	So (it was). And We knew all concerning him.
18:92	Then followed he (another) way.	Then he followed a road
18:93	Until, when he reached (a tract) between two mountains, he found, beneath them, a people who scarcely understood a word.	Till, when he came between the two mountains, he found upon their hither side a folk that scarce could understand a saying.
18:94	They said: "O Zul-qarnain! the Gog and Magog (people) do great mischief on earth: shall we then render thee tribute in order that thou mightest erect a barrier [wall] between us and them?"	They said: "O Dhu'l-Qarneyn! Lo! Gog and Magog are spoiling the land. So may we pay thee tribute on condition that thou set a barrier [wall] between us and them?"
18:95	He said: "(The power) in which my Lord has established me is better (than tribute): help me therefore with strength (and labour): I will erect a strong barrier [wall] between you and them:	He said: "That wherein my Lord hath established me is better (than your tribute). Do but help me with strength (of men), I will set between you and them a bank [wall]."
18:96	"Bring me blocks of iron." At length, when he had filled up the space between the two steep mountain sides, he said, "Blow (with your bellows)" then, when he had made it (red) as fire, he said: "Bring me, that I may pour over it, molten lead."	"Give me pieces of iron" - till, when he had leveled up (the gap) between the cliffs, he said: "Blow!" - till, when he had made it a fire, he said: "Bring me molten copper to pour thereon."
18:97	Thus were they made powerless to scale it or to dig through it.	And (Gog and Magog) were not able to surmount, nor could they pierce (it).
18:98	He said: "This is a mercy from my Lord: but when the promise of my Lord comes to pass, He will make it into dust; and the promise of my Lord is true."	He said: "This is a mercy from my Lord; but when the promise of my Lord cometh to pass, He will lay it low, for the promise of my Lord is true."
18:99	On that day We shall leave them [Gog and Magog] to surge like waves on one another: the trumpet will be blown, and We shall collect them all together.	And on that day we shall let some of them [Gog and Magog] surge against others, and the Trumpet will be blown. Then We shall gather them together in one gathering.

The Qur'anic version of the story then can be summarised as follows:
i.Muhammad is asked about someone called Zul-Qarnain
ii.God tells us he spoke to Z-Q, favouring him and enabling him to achieve his ends.
iii. God tells us Z-Q went west and reached the setting sun where he found a people.
iv. He then goes east and and discovers another people at the place where the sun rises. 
v. He sets off again until he discovers another people living in fear of two triibes called Gog and Magog beyond two mountains. 
vi. He erects a great wall made of iron and molten lead to protect them but says one day God will break it down.

Why should we then believe that Zul-Qarain is Alexander the Great, apart from the Islamic sources themselves which were unequivocal in their support of the belief?
Well, let me lay out just some of the plentiful evidence.
a. Zul-Qarain translates as Possesses Two Horns or The Two Horned One. Alexander was depicted with the horns of Ammon as a result of his conquest of ancient Egypt in 332 BC and was consequently known throughout the conquered world as The Two Horned One. Archaeologists have found a large number of different types of ancients coins depicting Alexander the Great with two horns. Indeed,  in the late 2nd century BC, silver coins depicting Alexander with ram horns were even used as a principal coinage in Arabia.
b. Ancient stories recount how Alexander built a great wall to keep out a people known as Gog and Magog:  "The building of gates in the Caucasus Mountains by Alexander to repel the barbarian peoples identified with Gog and Magog has ancient provenance and the wall is known as the Gates of Alexander or the Caspian Gates. The name Caspian Gates originally applied to the narrow region at the southeast corner of the Caspian Sea, through which Alexander actually marched in the pursuit of Bessus in 329 BC, although he did not stop to fortify it. It was transferred to the passes through the Caucasus, on the other side of the Caspian, by the more fanciful historians of Alexander." link . Gog and Magog have been associated with the Alexander legend since ancient times. In the Syriac Christian legends for example, Alexander the Great encloses the Gog and Magog horde behind a mighty gate between two mountains, preventing Gog and Magog from invading the Earth. In addition, it is written in the Christian legend that in the end times God will cause the Gate of Gog and Magog to be destroyed, allowing the Gog and Magog horde to ravage the Earth.
c. The story of Alexander travelling to the setting of the sun was well known and is even referred to by Ibn Kathir:  As for the idea of his reaching the place in the sky where the sun sets, this is something impossible, and the tales told by storytellers that he traveled so far to the west that the sun set behind him are not true at all. Most of these stories come from the myths of the People of the Book [Jews and Christians] and the fabrications and lies of their heretics. This suggests that  Ibn Kathir was aware of the Christian legends and thought they were referring to the same figure as the Zul-Qarnain mentioned in the Qur'an.

Given the remarkable similarities between the stories of Alexander and the episodes recounted in the Qur'an of Zul-Qarnain, the fact that Islamic theologians of ancient times identified them as one and the same man, and that Christian and Jewish stories also recount Alexander's exploits and refer to him as a holy man or even a saint, it seems utterly bizarre that Muslims should now try to deny the link.

So why should certain Muslims be so keen to do so?

Let's look at a typical site, Islamawareness.net. In an article entitled Why Zul Qarnain is not Alexander the author, a certain Khalid Jan, presents his "evidence". It can be summarised as follows: the Qur'an tells us that Zul-Qarain was a man beloved of God to whom God had extended special privileges and powers. Historical evidence, however, points indisputably to Alexander being a warlike, violent, pagan who worshiped pagan gods and who wanted to rule the world to gain riches.  (For completeness' sake we should note that Khalid fails to mention another reason why Muslims might be embarrassed to find God supposedly giving Alexander great powers: that of his well documented bi-sexuality and  long lasting love affair with Hephaestion )
Khalid concludes that it must therefore be impossible that the figure described in the Qur'an is Alexander.
Because the Qur'an can't be wrong.
That's it.

Generously, Khalid doesn't blame those who erroneously conflated the two figures because "academic and scientific knowledge was either limited or non-existent". (Unlike nowadays, eh Khalid?) He concludes:
The only common factor on which these scholars based their opinions is the expeditions carried by Alexander and Zul_Qarnain. Other than this, there are hardly any other characteristics that are common in both. The article thus dismisses the overwhelming evidence pointing to the figures being one and the same in a single line.

Hence we are left with a conundrum. Despite Islamawareness.net and others' attempts to convince us otherwise, it is as clear to modern readers as it was to the Islamic scholars that Zul-Qarain is Alexander the Great. It is also clear that Alexander was a pagan war-lord. Muslims cannot deny this since many of them, ironically, use the fact to "prove" that Zul-Qarain cannot be Alexander. 

How then can the Qur'an describe him as a God-fearing, Allah-worshipping, saintly individual to whom God actually spoke (usually a fool proof sign of a prophet, by the way)? 

Unless, that is, when Muhammad was asked by the Quraysh at the behest of some local rabbis what he knew about Zul-Qarnain, the "saintly" figure who conquered the ancient world, to test his prophet-hood, he simply recounted the relevant myths and legends that were common at the time (after taking fifteen days to do some research, of course.) How was he to know that many centuries later Alexander would be revealed as  a pagan who thought he was a god born of a god who was devoted to his male lover just to embarrass Muslim apologists and prove the Qur'an was written by a fallible human?

They (the rabbis) said, 'Ask him about three things which we will tell you to ask and if he answers them then he is a Prophet who has been sent (by Allah); if he does not, then he is saying things that are not true, in which case how you will deal with him will be up to you. Ask him about some young men in ancient times, what was their story? For theirs is a strange and wondrous tale. Ask him about a man who travelled a great deal and reached the east and the west of the earth. What was his story? And ask him about the Ruh (soul or spirit) —what is it? If he tells you about these things, then he is a Prophet, so follow him, but if he does not tell you, then he is a man who is making things up, so deal with him as you see fit.'(Tafsir Ibn Kathir)
The famous story in the Sira relates that when Muhammad was informed of the three questions from the Rabbis, he declared that he would have the answers in the morning. However, Muhammad did not give the answer in the morning. For fifteen days, Muhammad did not answer the question. Doubt in Muhammad began to grow amongst the people of Mecca. Then, after fifteen days, Muhammad received the revelation that is Sura Al-Kahf ("The Cave") link