Necesitaría conocer el sistema mas o menos completo, para darte consejos de diseño de datos. No puedo hablar en el aire, y en sobre lo poco que se entiende de tu estructura de base.
En cuanto a lo que necesitas para usar búsquedas como las que describo, no hay mucho más de lo que ya dije: Las tablas deben ser si o sí MyISAM (no pueden usarse InnoDB), se deben definir indices FULLTEXT sobre ese campo, y en las consultas se usa MATCH() AGAINST(), cuya descripción puedes leer detalladamente en el manual.
MySQL 5.0 Reference Manual :: 12 Funciones y operadores :: 12.7 Funciones de búsqueda de texto completo (Full-Text)
Te recomiendo leer con cuidado el tema de restricciones de ese tipo de busquedas, así como comprender correctamente el concepto de "relevancia" que se aplica: Es más relevante, mientras menos veces aparece el texto en la tabla.