Você deve usar índices de texto completo (você disse que não pode), projetar uma pesquisa de texto completo por conta própria ou descarregar a pesquisa do MySQL e usar o Sphinx/Lucene. Para o Lucene, você pode usar a implementação do Zend_Search_Lucene do Zend Framework ou usar o Solr.

Índices normais no MySQL são B+Trees, e eles não podem ser usados ​​se o início da string não for conhecido (e este é o caso quando você tem curinga no início)

Outra opção é implementar a pesquisa por conta própria, usando a tabela de referência. Divida o texto em palavras e crie uma tabela que contenha a palavra, record_id. Em seguida, na pesquisa, você divide a consulta em palavras e pesquisa cada uma das palavras na tabela de referência. Desta forma, você não está se limitando ao início de todo o texto, mas apenas ao início da palavra dada (e você combinará o restante das palavras de qualquer maneira)