Acabo de realizar pruebas acerca de dichas sentencias y de casi 3 mins bajo a 8 segundos es una impresionante velocidad usando 1 indice por cada campo dentro del where.
Creo que esta es la mejor forma de acelerar la velocidad pero aumentando el tamaño de la BD.
