es gibt ja einen volltext-index für mysql:
http://dev.mysql.com/doc/mysql/en/Fulltext_Search.html
das dürfte eigentlich schnell genug sein.

je nachdem, welche felder noch abgefragt werden im
select, entscheidet mysql ja, welcher index benutzt wird.
hmm, vielleicht hab ich auch ein paar tage urlaub, dann
würd ich mir das mal genauer ansehen...