Aha, questa volta l'ho capito per davvero.
Credo che il mio problema fosse l'utilizzo di NaviCat per aggiornare le regole di confronto. Ho una versione precedente di NaviCat, forse era un bug o qualcosa del genere.
Fare:
ALTER TABLE search CONVERT TO CHARACTER SET utf8 COLLATE utf8_general_ci;
risolto correttamente.
Usa sempre la riga di comando, ragazzi! =)