My question is that since all the Surahs of Quran start with bismillah, why doesn't Surah Taubah start with it?
An answer with reference to an authentic Hadith or so would be appreciated.
The Basmalah was not mentioned in the beginning of this Surah because the Companions did not write it in the complete copy of the Qur'an (Mushaf) they collected, following the Commander of the faithful, Uthman bin Affan, may Allah be pleased with him. (From tafsir ibn Kathir)
The 3rd opinion is based on the fact that some sahaba said that this surah before the abrogation of some verses had the length of surat al-Baqarah and has also an origin in a statement of 'Othman ():
وقال مالك فيما رواه ابن وهب وابن القاسم وابن عبد الحكم : إنه لما سقط أولها سقط " بسم الله الرحمن الرحيم " معه
(My own translation take it carefully) - - -
Imam Malik has said according to what has been narrated on the authority of (his students) ibn Wahb, ibn al-Qassim and ibn 'Abdalhakam: When its beginning has been taken away (abrogated) also "Bismillahi ar-Rahmani ar-Rahim: In the name of Allah , the Entirely Merciful, the Especially Merciful." has been left aside.
Some of the scholars of the tabi'yn like Kharijah خارجة (one of the 7 scholars of Medina) and abu 'Ismah أبو عصمة said: When they compilled the moshafs (written copies of the Quran) at the time of 'Othman the sahaba had a difference on whether at-Tawbah and al-Anfal are different surahs or the same so they kept a space between both as a compromise between both parties.
The fifth view is based on a statement of ibn 'Abbas ()(which is quoted in al-Mustdrak of al-Hakim)
قال عبد الله بن عباس : سألت علي بن أبي طالب : لم لم يكتب في ( براءة ) " بسم الله الرحمن الرحيم " ؟ قال : لأن " بسم الله الرحمن الرحيم " أمان و ( براءة ) نزلت بالسيف ليس فيها أمان . (My own translation take it carefully) - - -
Abdullah ibn 'Abass said: I've asked Alib ibn abi talib: Why they didn't write in Bara'ah "Bismillahi ar-Rahmani ar-Rahim"? He answered: Because "Bismillahi ar-Rahmani ar_Rahim" is a gurantee (or safety ) while Bara'ah has been revealed with the sword (meaning in order to make an end to the treaty of al-Hudaybiyah) without any (promise of) safety.
Al-Mubarrad المبرد has narrated the meaning of this narration and added: that's why they have not put them together as "Bismillahi ar-Rahmani ar-Rahim" is mercy while Bara'ah was reveald as a annoyance. Sufyyan ibn 'Oyaynah سفيان بن عيينة said something similar: "At-tasmiyah (Basmalah) is mercy and mercy is safety and this surah has been revealed about the hypocrites and with the sword and there's no safety for the hypocrites.
Al Qurtoby then said the most correct view is that the basmalah has not been put in because Jibrel () didn't reveal it in this surah this was said by al-Qushayri and in a statement of 'Othman saying:
The Messenger of Allah (All Prayers and Blessings of Allah be upon him) died, but he did not mention to us that surah al-bara'ah is a part of al-anfal.
(Sunan abi Dawod, note this hadith is an additional statement of the former quoted hadith, so ibn 'Abbas is repeating the answer of 'Othman when asked)
is a proof that all the surahs of the Quran have been ordered according our Prophets () orders and explanations with the exception of Bara'ah which has been added to al-Anfal without an agreement of the Prophet () because he died before clearing this Issue. But as the two surahs were called the two mates القرينتان (al-Qarinatan) it was a clear conclusion to put them together one before the other. As both were known as mates during the lifetime of the Prophet ().
Note that one can merge all of these reasons together as for example reason 1 and 5 are saying more or less the same. While 2-4 are also saying the same. So we have on one hand the fact that the content of the Quran is divine and the order of verses is mostly ordered by our Prophet () (one could say it is divine) so the fact that al-basmalah in this surah is not in the Quran is simply because it was not revealed in this position, if we add the circumstances of the verse and the meaning of this surah we can conclude that adding al-Basmalah from the perspective of Arabs of that time would be meanles if not contradictory to the message they wanted the hypocrites, disbelievers and pagans to conclude from it.
On the dispute whether the Basmalah at the beginning of the surahs is part of the Quran
Note that there's a dispute among scholars whether the Basmalah is part of each surah of the Quran except Bara'ah (where there's no dispute about it not being at the begin of this surah) and in surat an-Naml (where there's no doubt of it being part of the content of the surah).
So they agree that it is indeed compiled in the moshaf copies (in the middle of surat an-Naml and at the beginning of 113 surahs, Bara'ah is the only exception!), but they disagree on the matter whether it is part of the Quran (the words of Allah which have been transmitted orally from generation to generation) when it comes to those 113 occasions where it is written at the beginning of a surah! One could say the dispute isn't about it being Quran, but on whether the repetitions are also Quran.
It is not a verse neither at the beginning of al-Fatiha nor of any other surah this was the opinion of scholars such as Malik, al-Awza'i and all the scholars of a-Shaam, Basra and al-Medina with the exception of Abdullah ibn 'Amr and ibn Shihaab. One source for that is the sahih hadith, which doesn't quote al-Basmalah as part of al-Fatiha. Imam az-Zamakhsahri added abu Hanifa to those who hold this opinion. Here an other source for this opinion. the maliki schol clearly say that it was put in the Quran in order to get the blessing of Allah as there's a hadith (see also in sunan abi Dawod) which has been also quoted or interpreted in this version:
Every important matter that does not start with "In the name of Allah , the Entirely Merciful, the Especially Merciful", is devoid (of blessings).
It is a verse at the begining of surat al-Fatiha only this is the opinion of Imam a-Shafi'i (in one of his two statements), Imam Ahmad, Ishaaq, abu Twar and the scholars of Mekka and al-Kufa (not including abu Hanifa). (Note that Imam a-Shafi'i has grown up in Mekka and the riwaya of ibn Kathir al-Makki is the only one that emphasizes on the fact that al-Basmalah is part of al-Fatiha but both the kufi and makky count of verses count al-Basmalah as verse 1:1, for further information you may refer to my answer on How many ayaths are there in Al-Quran?) one of their sources is what was narrated by Um Salamah and abu Hurairah.
It is a verse in each surah and was revealed to make a distinction between two surahs (in this Arabic thread they say it is the opinion of the majority) this is the second statement of Imam a-Shafi'i and Abdullah ibn al-Mubarak. The source for this is this hadith.
Source at-tahrir wa tanwir of sheikh Taher ibn Achour.