Deux pistes :

crée une copie de ta table avec un CREATE SELECT, indexe ta copie, et remplace l'original par la copier
passe ta table en InnoDB, puis remets-la en MyISAM