The following answer was given by Faqihul Ummah Hadhrat Mufti Mahmood Gangohi (rahmatullah alayhi) to the question why Surah Taubah has no Bismillah at the beginning.
When Hadrat Uthman رضى الله عنه was asked why there was no bismillah at the beginning of Surah al-Tawba like how there is bismillah at the beginning of other surahs, he replied that there was some doubt as to this surah being a separate surah, because Nabi صلى الله عليه و سلم passed away without explicitly mentioning anything regarding it. This is why Bismillah was not written at the beginning of Surah Taubah. However, since its subject-matter is similar to that of Surah Anfal, it was placed after it and a space for Bismillah has been kept because it is possible that this is a separate surah. (Tirmizi, Vol 2, Pg.139)
In Bukhari Shareef (Vol 2,Pg 271) it is mentioned that this surah was revealed to cancel the peace treaty. In it appears the command of killing the mushrikeen (polytheists) and the expression of Allah Ta`ala’s anger over them. Therefore, Bismillah was not written at the beginning of the surah since Bismillah signifies peace and mercy.
It appears in Shaatbi: لتنزيلها بالسيف لست مبسملا (Bismillah does not appear at the beginning of this surah, because it was revealed in connection to war.) This is not the actual reason though it is a point to consider. The actual reason is that which is narrated from Hadrat Uthman رضى الله عنه (Bayanul Qur’an, Vol 4, Pg 95)