Você precisa definir um collation específico em seu esquema para que o MySQL saiba quais caracteres devem ser equivalentes. Se uma letra com um sinal diacrítico é considerada igual a uma sem ou alguma outra sequência de caracteres depende do idioma, mas tente utf8_general_ci como ponto de partida para ignorar acentos (supondo que você esteja usando um conjunto de caracteres UTF-8, que você deve ser realmente).

Tente usar o mesmo agrupamento em todas as suas strings, para que elas possam ser unidas e comparadas sem conversões caras e que quebram o índice.