O novo recurso de pesquisa de texto completo do InnoDB no MySQL 5.6 ajuda neste caso. Eu uso a seguinte consulta:
SELECT MATCH(column) AGAINST('(word1* word2*) ("word1 word1")' IN BOOLEAN MODE) score, id, column
FROM table
having score>0
ORDER BY score
DESC limit 10;
onde
( ) agrupa palavras em uma subexpressão. O primeiro grupo tem like word% significado; o segundo procura a frase exata. A pontuação é retornada como float. 
