Работа с MyISAM таблицей с кол-вом записей от 10'000'000?
(опциональный шаг:
MyISAM — На свалку.
Базу — в InnoDB.
)
Про fulltext Забудьте — он вам столько геморроя доставит, не вылечитесь.

В качестве поискового индекса используйте мегабыстрый опенсорсный зрелый sphinx.
> индексы по полям, как я понимаю, особо не помогут

Это с чего это вдруг?