Exactamente, creo que tu problema es de mezcla de tocino con velocidad, estás usando sentencias MySQl en medio del código PHP, la solución de Genetix es la buena en tu caso. Si tienes mysql 4.0 puedes incluso hacer búsquedas "inteligentes" por medio de un index y de Full-Text search. Más info en
http://dev.mysql.com/doc/mysql/en/Fulltext_Boolean.html