Zoals MartinK zegt, als je tabel maar een paar honderd rijen heeft, zou je zoekopdracht vrij snel moeten zijn, zelfs zonder optimalisatie - het is de moeite waard om te controleren wat er aan de hand is.
De beste manier om tekstvelden te doorzoeken is echter door gebruik te maken van volledige tekstindexering (http://dev.mysql.com/doc/refman/5.0/en/fulltext-search.html) - dit is precies ontworpen voor het geval dat u' opnieuw beschrijven.