Question: There is a Qur’anic verse (9:29)¹ that states that we should fight the Ahl al-Kitab (the People of the Book) until they pay the Jizyah tax. Then we also have verses like 9:5² which state that the Idolaters should be put to death. The following Hadith also contains a similar directive:

I have been directed to fight against these people until they testify to the oneness of God and to the prophethood of Muhammad, establish the prayer and pay Zakah. (Muslim: No. 22)

    So are we required to kill Idolaters and spare the People of the Book if they pay Jizyah?
    Answer: Neither of these inferences is correct. Since these verses and the Hadith you have quoted have a specific context and background, I’ll try to explain this context, which, hopefully, will bring out the true purport of these verses:
    It is evident from the Qur’an³ that the basic truths for which man shall be held accountable on the Day of Judgement are:
    1. Belief in the One and Only God.
    2. Belief that a person shall be held accountable on the Day of Judgement.
    3. Belief that this accountability shall be based on the deeds a person does in this world.
    The Almighty selects and sends certain personalities called Messengers (Rusul) to elucidate and explain these basic truths to their respective people. With His special help and assistance, they remove misconceptions which may surround these concepts and vehemently say that if people do not accept these truths they shall be doomed in this world and in the Hereafter too. People who deliberately deny these truths are punished in various degrees in this world so that this whole episode can become an argument for the reward and punishment that is going to take place on similar grounds in the Hereafter. In the language of the Qur’an, this process of delineating the truth in its ultimate extent so that no one is left with an excuse to deny it is called shahadah ‘ala al-nas (bearing witness to the truth before other people) and those who establish it are called shuhada (witnesses to the truth).
    According to the Qur’an, Muhammad (sws) and his Companions (rta) were conferred this status by the Almighty:

And similarly, O Companions of the Prophet! We have made you an intermediate group so that you be witnesses [of this religion] before [other] nations, and the Rasul be such a witness before you. (2:143)⁴

    So Muhammad (sws), like the previous Messengers, explained these truths in their ultimate form through the special help of the Almighty. When it became evident that his addressees were deliberately denying him, they were punished in varying degrees to prove to mankind for the last time that a similar court of justice shall be set up on the Day of Judgement, and that the reward and punishment given by the Almighty through His Prophets (sws) to their addressees in this world would be given in the Hereafter to all the people who deny such basic truths. The Idolaters of Arabia were given the options of accepting faith or death and the People of the Book were given the options of accepting faith or remaining subservient by paying Jizyah, a tax imposed on them. This difference seems to stem from the fact that the Idolaters subscribed to polytheism even after being convinced about its baselessness, while the People of the Book were basically monotheistic though were involved in certain polytheistic practices. We know from the Qur’an that polytheism is something which the Almighty will never forgive simply because those who associate partners with Him have no divine sanction for this:

God never forgives those guilty of polytheism though he may forgive other sins to who He pleases. Those whom commit polytheism devise a heinous sin. (4:48)

    It also needs to be appreciated that it is the Almighty who actually punished people who knowingly denied the truth as revealed by His Messengers. His Messengers and their Companions in this exercise were no more than agents of His retribution. The Qur’an asserts:

Fight them [O Believers!] and God will punish them with your hands and humiliate them. (9:14)

It is not you [O believers] who slew them; it was [ in fact] Allah [who slew] them. (8:17)

    After Muhammad (sws), his immediate Companions (rta) in the background of the shahadah established by him extended this shahadah through their collectivity to various other nations of the world. They subsequently waged war against these nations to punish them for their deliberate denial.
    As far as the Hadith⁵ you have referred to is concerned, it must be understood in the light of 9:5. If understood thus, it relates to the Idolaters of Arabia who were to be put to death if they refused to accept Islam. Consequently, another text of this Hadith specifically mentions them by name:

Anas Ibn Malik reports from the Prophet: ‘I have been directed to fight against these Idolaters until they testify to the oneness of God and to the fact that Muhammad is his servant and messenger. If they testify to the oneness of God and to the fact that Muhammad is his servant and prophet, establish our prayer and face our Qiblah [while praying], and eat our slaughtered animals, their life and wealth we shall hold sacred except if they commit some violation. (Nasa’i: No. 3966)

    It is evident from this analysis that verses like 9:5 and 9:29 and Ahadith of similar meaning specifically relate to the age of the Prophet (sws) and his Companions (rta). After their departure, no Muslim preacher can deliver the truth in its ultimate form and neither has he any means to know if his addressees are deliberately denying him. In other words, after them, no one can establish the shahadah.
    Muslims of today must realize  this difference and not insist on doing something which is the prerogative of only the Prophets of Allah and their companions. Therefore, today Muslims cannot wage war on the non-Muslims of the world to forcibly make them accept faith. They must keep on presenting Islam to them in a polite and humble manner.