As designed. Wenn du bei einer Like-Abfrage als erstes Zeichen ein Wildcard hast so muß die Datenbank einen Full-Table-Scan durchführen da kein vorhander Index mehr verwendet werden kann.
Wieviel Speicher darf der
MySQL-Server verwenden? Evtl. wird es schneller wenn der Index komplett im Speicher gehalten werden kann und damit "nur" ein kompletter Indexdurchlauf nötig ist.