Aha, diesmal habe ich es wirklich herausgefunden.
Ich glaube, mein Problem war die Verwendung von NaviCat zum Aktualisieren der Sortierung. Ich habe eine ältere Version von NaviCat, vielleicht war es ein Fehler oder so etwas.
Tun:
ALTER TABLE search CONVERT TO CHARACTER SET utf8 COLLATE utf8_general_ci;
richtig korrigiert.
Verwenden Sie immer die Befehlszeile, Kinder! =)