In truth, there is no total freedom of non-Islamic religions in Islam. Instead, they are relegated to a lower status to Islam or are completely intolerable, which Allah and His apostle made very clear towards the ending stage of the prophet's career. We have to go back to the verse 9:1-5 mentioned above to explain these issues.
The terms, negotiated by Abu Sufyan, under which the Quraysh were allowed to keep their religion on the day of conquest of Mecca, has been outlined above as accounted by Ibn Ishaq. However, one recalcitrant group of Meccans, who are said to have fallen on the way of Khalid al-Walid's army, showed a meek resistance and Khalid slaughtered those fallen within his reach and pursued others running for their lives.
Although many Quraysh embraced Islam on that day, there were some who apparently persisted on practicing idolatry and they were allowed to enter the Ka'ba for worships but on paying toll to the Muslim guardian appointed by the Prophet. The Prophet now wanted to do away with the practice of idolatry not only in Ka'ba but the rest of Mecca and elsewhere. To achieve this goal, the verse 9:1-5 (slay the pagans wherever ye find them etc.) were revealed, which will be discussed more in detail here.
Now consider the verse 9:2 & 9:3:
[Q 9:2] Go ye, then, for four months, backwards and forwards, (as ye will), throughout the land, but know ye that ye cannot frustrate Allah (by your falsehood) but that Allah will cover with shame those who reject Him.
[Q 9:3] ...If then, ye repent, it were best for you; but if ye turn away, know ye that ye cannot frustrate Allah. And proclaim a grievous penalty to those who reject Faith.
So, Allah warned that the pagans were frustrating Him by sticking to paganism and urging them to repent and submit to Islam or else face Allah's wraths. However, they could only vacillate (go backwards and forwards) for another four months.
On the day of conquest of Mecca the earlier year, Allah and his apostle had promised the safety of the pagans at the pain of accepting defeat and acceding their territory to the Muslim rule. But how does the frustrated Allah, Who has lost patience by now, make those remnant pagans accept Islam unconditionally? Find it out in verses 9:1 and 9:3:
[Q 9:1] Freedom from obligation (is proclaimed) from Allah and His messenger toward those of the idolaters with whom ye made a treaty.
[Q 9:3] And a proclamation from Allah and His messenger to all men on the day of the Greater Pilgrimage that Allah is free from obligation to the idolaters, and (so is) His messenger....
Here, Allah and His apostle abruptly break the treaty or obligation of protecting the idolaters made the earlier year. Once made Himself arbitrarily free of any obligation to the pagans, here is how He plots the complete annihilation of the vestiges of idolatry in verse 9:5.
[Q 9:5] But when the forbidden months are past, then fight and slay the Pagans wherever ye find them, an seize them, beleaguer them, and lie in wait for them in every stratagem (of war); but if they repent, and establish regular prayers and practise regular charity, then open the way for them: for Allah is Oft-forgiving, Most Merciful.
Once the forbidden months, that is, the grace period of four months (Q 9:1, 9:4) is over, kill the idolaters wherever you find them and you can use every strategic and deceptive means to accomplish this final goal of Allah. However, they will be spared only if embraced Islam and performed all the rituals and obligations binding on the Muslims. Hence, according to the Koran, the freedom of religion in Islam for the pagans/idolaters (like the Hindus, Buddhists and Taoists etc.) is acceptance of Islam or death. This is how Allah becomes Oft-forgiving and Most Merciful.
Finally in verse 9:28, Allah specify that complete prohibition of the pagans to enter the Ka'ba.
[Q 9:28] O ye who believe! Truly the Pagans are unclean; so let them not, after this year of theirs, approach the Sacred Mosque. And if ye fear poverty, soon will Allah enrich you, if He wills, out of His bounty, for Allah is All-knowing, All-wise.
Now that the Ka'ba had been cleansed of idolatry, the Prophet could make his pilgrimage the following year in 632, which was also incidentally his last Hajj (farewell Hajj).
How about the Christians and Jews? Now that position of the idolaters in Islam has been made clear, I will now allude to the final status ordained to the Christians and Jews (people of the book) in Islam. Let us turn to verse 9:28 again. After prohibiting the entry of idolaters for worship and pilgrimage to Ka'ab, Allah recounts the worries of the Muslims as follows:
[Q 9:28] ...And if ye fear poverty, soon will Allah enrich you, if He wills, out of His bounty, for Allah is All-knowing, All-wise.
How this fear of poverty is linked to the prohibition of the entry of the idolaters in Ka'ba? It is because, the Ka'ba had traditionally been a source of great revenue from tips/toll paid by pilgrims coming from far-flung places around Arabia. For this reason, the guardianship of Ka'ba had been the most coveted object amongst the Mecca tribes and was the centre of many disputes and dissensions. When the idolaters are not allowed to enter the Ka'ba, from where to get the lost revenues? It should be understood that in the original Islamic rules, Muslims are supposed to pay only the Zakat (2.5% of produce, profits) and nothing else. This practice was in vogue during the early period of Islam.
And here in verse 9:29, Allah devise the policy of making up for the lost revenues (from the Ka'ba) as promised in verse 9:28 (soon will Allah enrich you...):
[Q 9:29] Fight those who believe not in Allah nor the Last Day, nor hold that forbidden which hath been forbidden by Allah and His Messenger, nor acknowledge the religion of Truth, (even if they are) of the People of the Book, until they pay the Jizya with willing submission, and feel themselves subdued.
The stubborn Jews and Christians, the so-called people of the book in Islam, need not convert to Islam. They can keep their religion by accepting subjugation and submission to the Muslim rule and paying Jizyah, which was to make up for the revenues lost from the coffer of Ka'ba as a result of complete prohibition of idolatry.
Idolatry, which is out and out disapproved by Allah, cannot be tolerated. However, the people of the book, despite the faulty and unperfected nature of their religion, can be tolerated but at a price, which is accepting subjugation (lower status) to the supreme and perfect truth of Islam and by paying the Jizyah. After all, same Allah was the architect of those religions which must contain His partial truth and guidance. On the hand, religion of idolatry, paganism or heathenism holds no truth but complete falsehood and is an affront to the almighty creator and must be annihilated.
Modern educated Muslims' spreading the cooked-up notion of Islam's according 'total religious freedom to all other religions', thus, amounts to misinforming, misleading and spreading falsehood. This has been called the spreading of mischief and hypocrisy, that is, fitnah or al-fasad in the Islamic jargons. The punishment for spreading fitnah in Islam is death, crucifixion or cutting-off hands and feet from opposite ends.