Aha, descobri por reais desta vez.

Acredito que meu problema estava usando o NaviCat para atualizar o agrupamento. Eu tenho uma versão mais antiga do NaviCat, talvez tenha sido um bug ou algo assim.

Fazendo:

ALTER TABLE search CONVERT TO CHARACTER SET utf8 COLLATE utf8_general_ci;

corrigi-lo corretamente.

Sempre use a linha de comando, crianças! =)