Както казва MartinK, ако вашата таблица има само няколкостотин реда, заявката ви трябва да бъде доста бърза дори без оптимизация - струва си да проверите какво се случва.
Въпреки това, най-добрият начин за търсене в текстови полета е да използвате индексиране на пълен текст (http://dev.mysql.com/doc/refman/5.0/en/fulltext-search.html) - това е предназначено точно за вашия случай повторно описвам.
