Cuando tienes que hacer búsquedas efectivas en volumen de datos importantes, como es tu caso, lo ideal es utilizar búsquedas booleanas(MATCH, AGAIN), tendrias que crear indices de texto completo(FULL TEXT) y utilizar la potencia de este tipo de búsquedas.
Hay un artículo muy bueno sobre búsquedas booleanas en
www.mysql-hispano.org, seguro que te sirve
un saludo!