LIKE fará uma varredura completa da tabela se você tiver um % no início do padrão.

Você pode usar FULLTEXT no modo booleano (em vez de linguagem natural) para evitar a regra de 50%.

http://dev.mysql.com/doc/refman /5.0/en/fulltext-boolean.html