Aha, kom på det på riktigt den här gången.
Jag tror att mitt problem var att använda NaviCat för att uppdatera sorteringen. Jag har en äldre version av NaviCat, det kanske var en bugg eller något.
Gör:
ALTER TABLE-sökning KONVERTERA TILL TECKENSETT utf8 SAMMANSTÄLL utf8_general_ci;
fixade det korrekt.
Använd alltid kommandoraden, barn! =)