Měli byste buď použít fulltextové indexy (řekli jste, že nemůžete), navrhnout si fulltextové vyhledávání sami nebo přenést vyhledávání z MySQL a použít Sphinx/Lucene. Pro Lucene můžete použít implementaci Zend_Search_Lucene ze Zend Framework nebo použít Solr.
Normální indexy v MySQL jsou B+Trees a nelze je použít, pokud není znám začátek řetězce (a to je případ, kdy máte na začátku zástupný znak)
Další možností je implementovat vyhledávání na vlastní pěst pomocí referenční tabulky. Rozdělte text na slova a vytvořte tabulku, která obsahuje slovo, record_id. Poté při hledání rozdělíte dotaz na slova a vyhledáte každé ze slov v referenční tabulce. Tímto způsobem se neomezujete na začátek celého textu, ale pouze na začátek daného slova (a zbytek slov stejně spárujete)