Debería usar índices de texto completo (dijiste que no puedes), diseñar una búsqueda de texto completo por ti mismo o descargar la búsqueda de MySQL y usar Sphinx/Lucene. Para Lucene, puede usar la implementación Zend_Search_Lucene de Zend Framework o usar Solr.
Los índices normales en MySQL son B+Trees, y no se pueden usar si no se conoce el inicio de la cadena (y este es el caso cuando tiene un comodín al principio)
Otra opción es implementar la búsqueda por su cuenta, usando la tabla de referencia. Divida el texto en palabras y cree una tabla que contenga la palabra, record_id. Luego, en la búsqueda, divide la consulta en palabras y busca cada una de las palabras en la tabla de referencia. De esta manera, no se limita al comienzo de todo el texto, sino solo al comienzo de la palabra dada (y de todos modos coincidirá con el resto de las palabras)
