It seems to me the answer is much simpler, and has already been mentioned earlier in this thread.
To repeat what I said in elsewhere on the forum, I think
The Horse and His Boy is quite clearly modelled upon
One Thousand and One Arabian Nights, a Persian collection (the source isn't completely clear; the 'Thousand Stories' or Hazâr Afsâna, has been suggested as one possibility. However, what is certain is that they are Persian, perhaps including elements of Indian and Arabic story telling as well. Its original title is The Book of One Thousand and One Nights, Kitāb 'Alf Layla wa-Layla in Arabic, Hazâr-o Yak Šab in Persian).
Not only the setting, but also the style of
The Horse and His Boy is remniscent of the Persian precursor. For example, this little snippet could have come straight out of one of the tales:
The Horse and His Boy said:
Sometimes if Arheesh was there Shasta would say, "O my Father, what is there beyond that hill?" And then if the fisherman was in a bad temper he would box Shasta's ears and tell him to attend to his work. Or if he was in a peacable mood he would say, "O my son, do not allow your mind to be distracted by idle questions. For one of the poets has said, 'Application to business is the root of prosperity, but those who ask questions that do not concern them are steering the ship of folly towards the rock of indigence'."
The fisherman theme recurs throughout the original tales, but of course those are not what Lewis would have been familiar with. More likely he would remember translations and selections from his youth (remember he was born 1898, living in a house lined with books), such as various that are available on Project Gutenberg - that of
Andrew Lang (1844-1912),
John Payne (1850-1894) and perhaps the best known,
Sir Richard F. Burton (1821-1890). Aside from Project Gutenberg,
this is another good site containing translations of the tales, and for further info there is always
Wikipedia.
To take an example of a man in Arheesh's occupation, there is the famous story of the Fisherman and the Genie, which starts like this (in Payne's translation):
The Book of the Thousand Nights and One Night (1) said:
There was once a poor fisherman, who was getting on in years and had a wife and three children; and it was his custom every day to cast his net four times and no more. One day he went out at the hour of noon and repaired to the sea-shore, where he set down his basket and tucked up his skirts and plunging into the sea, cast his net and waited till it had settled down in the water. Then he gathered the cords in his hand and found it heavy and pulled at it, but could not bring it up. So he carried the end of the cords ashore and drove in a stake, to which he made them fast. Then he stripped and diving round the net, tugged at it till he brought it ashore. Whereat he rejoiced and landing, put on his clothes; but when he came to examine the net, he found in it a dead ass; and the net was torn. When he saw this, he was vexed and said: 'There is no power and no virtue save in God the Most High, the Supreme! This is indeed strange luck!' And he repeated the following verses...
The "O, my son" business is another indicator; to take another section from Payne:
..."O my son, I mean to give one to thy brother Zoulmekan and the other to thy sister Nuzhet ez Zeman." When Sherkan heard that he had a brother (for up to that time he had only known of his sister) he turned to his father and said to him, "O King, hast thou a son other than myself?" "Yes," answered Omar, "and he is now six years old." And he told him that his name was Zoulmekan and that he and Nuzhet ez Zeman were twins, born at a birth. This news was grievous to Sherkan, but he hid his chagrin...
..."O captain, I see nothing to right and left save sky and water, but ahead I see something looming afar off in the midst of the sea, now black and now white." When the captain heard the look-out's words, he cast his turban on the deck and plucked out his beard and buffeted his face and said, "O King, we are all dead men, not one of us can be saved." We all wept for his weeping and I said to him, "O captain, tell us what it is the look-out saw." "O my lord," answered he, "know that we lost our way on the night of the storm and since then we have gone astray one-and-twenty days and there is no wind to bring us back to our true course...
Then there is the depiction of the people. You'll see plenty of turbans:
Then he set his turban on top of the cane and tied a girdle round the middle of the effigy and planted it in the place where he used to say his prayers...The Khalif was pleased and said, 'O Kerim, put off thy clothes.' So he put off a gown of coarse woollen stuff, patched in a hundred places and full of disgusting vermin, and a turban that had not been unwound for three years, but to which he had sewn every rag he came across...
Along with scenes like this:
So he turned back and mounted and drew his scimitar; then he gave his horse the spur and he started off with him, like an arrow from a bow, whilst he brandished his naked blade and cried out, "God is Most Great!"
You'll also find plenty of Viziers:
...the elder king yearned after his brother and commanded his Vizier to repair to the latter's court and bring him to his own capital. The Vizier replied, "I hear and obey," and set out at once and journeyed till he reached King Shahzeman's court in safety...
One thing you won't find is polytheism. From what I've read, the
Thousand and One Nights, under all its various names, remains an Islamic text. There is mention of a 'devil', but it appears to be in a similar context to the Christian - I haven't found any demons, but then I'm doing a basic search in Word.
Furthermore, at the time Lewis was born, '
orientalism' would still have been a major influence on how people like Lewis might have thought of the mysterious 'East'. For example, this is the kind of thing painter Rudolf Ernst (1854-1932) was producing:
So, to conclude that mountain of quotes, my opinion is that the Calormenes are simply Lewis' version of the 'other', to provide Narnia with an antagonistic force. If your main characters are white-skinned, rather European-looking individuals, then the obvious counterpoint (for someone who hadn't travelled much and had memories of orientalism flitting about his head) is found in the exotic East. I don't think he intended them to be equated with Muslims, at least not in any direct sense. For me,
The Horse and His Boy is basically
The One Thousand and One Nights lands in Narnia, trailing stylistic fragments from its source.
Of course, it would be an incredibly bad idea to put the Calormenes into a film as they are in the books - todays climate is very different to the 1950s, and I can't see how dark, bearded men wearing turbans, living in a desert, wielding scimitars and worshipping a different god could
not cause offence, no matter how innocent Lewis' original intentions may or may not have been. The allegorical implications of
The Last Battle don't help much either, as that could very easily be interpreted as a conflict between two faiths - I can't think of a worse time to bring up that kind of theme in a cinematic format (
Kingdom of Heaven had to be very, very careful).