Ha jól számolok, és havonta van a bérszámfejtés, akkor ez kevesebb, mint 300000 adat. Az egy átlag mysql-nek sem lenne szabad megkottyanjon, nem hogy egy órán át tartson...
Egy időben elemeztem mysql kéréseket, és érdekes eredmény volt, hogy bizonyos esetekben, hiába volt meg az adott rendezés szerinti index, mégsem használta. Ilyen esetben direkt meg lehet mondani neki, melyik indexet használja. Persze, ha a kód nem módosítható, akkor ez is marad elméleti síkon.
Az explain kimenete tényleg tanulságos lehetne, anonimizálva is.