E>Full text index, имеющийся в MySQL, помочь не может, так как индексирует лишь целые слова, слишком короткие или частые игнорирует и т.д.

Проиндексировать все подстроки практически невозможно — их слишком много.

Реально индекс все-таки можно строить только по словам.

Если не работает (или ты не можешь настроить? или действительно он так устроен?) стандартный полнотекстовый индексатор — напиши свой. Это не так сложно.