И что мешает это всё равно заиндексировать?
Можно сделать массив `search` который будет содержать 2 вида строк: в нижнем регистре и в нижнем регистре без знаков.
Далее простой индекс по этому полю `search`, и затем поиск будет весьма продуктивен.
Главное это escape'ить регулярные знаки в прописные, например . в \. и т.п.
Далее поиск будет работать по таким запросам:
-=м.О.Й.к.л
мой
МоЙКЛаН
мо
-=м.
Что для поиска думаю вполне достаточно и гравное это будет очень быстрым поиском.