Трябва или да използвате пълнотекстови индекси (вие казахте, че не можете), да проектирате сами пълнотекстово търсене или да разтоварите търсенето от MySQL и да използвате Sphinx/Lucene. За Lucene можете да използвате реализация на Zend_Search_Lucene от Zend Framework или да използвате Solr.
Нормалните индекси в MySQL са B+Trees и не могат да се използват, ако началото на низа не е известно (и това е случаят, когато имате заместващ знак в началото)
Друга възможност е да приложите самостоятелно търсене, като използвате справочна таблица. Разделяне на текст в думи и създаване на таблица, която съдържа дума, record_id. След това в търсенето разделяте заявката на думи и търсите всяка от думите в референтната таблица. По този начин вие не се ограничавате до началото на целия текст, а само до началото на дадената дума (и така или иначе ще съпоставите останалите думи)
