Powinieneś użyć indeksów pełnotekstowych (mówiłeś, że nie możesz), samodzielnie zaprojektować wyszukiwanie pełnotekstowe lub odciążyć wyszukiwanie z MySQL i użyć Sphinx/Lucene. Dla Lucene możesz użyć implementacji Zend_Search_Lucene z Zend Framework lub użyć Solr.
Normalne indeksy w MySQL to B+Drzewa i nie można ich używać, jeśli nie jest znany początek ciągu (a tak jest w przypadku, gdy na początku masz symbol wieloznaczny)
Inną opcją jest samodzielne zaimplementowanie wyszukiwania przy użyciu tabeli referencyjnej. Podziel tekst na słowa i utwórz tabelę zawierającą słowo, record_id. Następnie w wyszukiwaniu dzielisz zapytanie na słowa i szukasz każdego ze słów w tabeli referencyjnej. W ten sposób nie ograniczasz się do początku całego tekstu, a jedynie do początku danego słowa (a i tak dopasujesz resztę słów)
