Tach!
Tut es auch in einer Kopie der tabelle ohne Index im phpmyadmin nicht. Und da EXPLAIN auch so gar nichts auffälliges zeigt: Kann das sein, dass mysql einen cache hat und der irgendwie gegriffen hat? Ich habe nämlich die 400 Einträge nur übrig gelassen. Zuvor waren ca. 1,7 Mio. Einträge in der Tabelle, wovon ich bis auch die 400 alle anderen gelöscht habe.
Dann kann man sich das erklären mit der immer noch großen Datei und dass ein Suchen darin langsam ist. Nach dem Entfernen einer solchen großen Menge kann man mit Optimize Table die Dateigröße an die aktuellen Gegebenheiten anpassen. Gibts auch als Funktion im PMA.
dedlfix.