Hola, yo tengo un problema parecido al tuyo, tengo una BD de unos 2 gigas y además ira creciendo.
Un par de post más arriba puse los indices que cree, pero no observo resultado, incluso, no se si ni si quiera están bien.
Otra cosa que he hecho es paginar las consultas, que eso si parece que me acelera un poco el tema.
Para ello use una movida que crearon los de php llamada paginator, aquí te dejo el enlace que lo explican todo:
http://taringa.net/posts/ebooks-tutoriales/1261574/Paginator-versi%C3%B3n-1_6---Paginacion-para-PHP-y-MySQL.html
Suerte y si encuentras otra solución factible, me cuentas.
Saludos.
