Dovresti usare gli indici full-text (hai detto che non puoi), progettare una ricerca full-text da solo o scaricare la ricerca da MySQL e usare Sphinx/Luce. Per Lucene puoi usare l'implementazione Zend_Search_Luce da Zend Framework o usare Solr.
Gli indici normali in MySQL sono B+Trees e non possono essere usati se l'inizio della stringa non è noto (e questo è il caso quando hai un carattere jolly all'inizio)
Un'altra opzione è implementare la ricerca in proprio, utilizzando la tabella di riferimento. Dividi il testo in parole e crea una tabella che contiene word, record_id. Quindi nella ricerca dividi la query in parole e cerchi ciascuna delle parole nella tabella di riferimento. In questo modo non ti stai limitando all'inizio dell'intero testo, ma solo all'inizio della parola data (e abbinerai comunque il resto delle parole)
