У нас была похожая ситуация около месяца назад, наша база данных была примерно 33k ~, и из-за того, что наш движок был InnoDB, мы не могли использовать функцию полнотекстового поиска MySQL (что довольно тупо).
Мы решили внедрить sphinxsearch (http://www.sphinxsearch.com)), и мы действительно впечатлены результатами (я стал его фанатом).
Если мы выполним поиск по большому индексу со многимистолбцы (множество левых объединений) всех наших строк, мы фактически вдвое сократили время ответа на запрос к аналогу MySQL 'LIKE'.
Хотя мы давно не использовали его - если вы собираетесь строить дляв будущем я бы порекомендовал сфинкса.