MySql kan index negeren als het index toegang geeft tot meer dan 30% van de tabelrijen. Je zou FORCE INDEX [index_name] kunnen proberen, het zal in ieder geval index gebruiken.
De waarde van sysvar_max_seeks_for_key is ook van invloed op het al dan niet gebruiken van de index:
-
http://dev.mysql.com /doc/refman/5.0/en/server-system-variables.html#sysvar_max_seeks_for_key
Probeer deze waarde te wijzigen in een kleiner getal.
Zoek naar soortgelijke verzoeken op SO.