Cita:
Iniciado por AlanChavez 
Define "muchos" registros, y "mucho tiempo".
Yo he utilizado expresiones regulares en tablas con millones de registros y las consultas se ejecutan en milisegundos, si es cierto que no son tan rápidas como un indice primario, pero que otra alternativa propones?
Si no quieres utilizar expresiones regulares en MySQL, entonces podrias hacer otra columna con el nombre normalizado utilizando solamente caracteres del alfabeto latino (o cualquier alfabeto que quieras) y busca esa columna.
Por ejemplo puedes las columnas:
Nombre, NombreCanonico
José, Jose
Jöse, Jose
Jœsë, Jose
Y cuando busques, utilizas:
SELECT N.Nombre FROM Nombres N WHERE N.NombreCanonico = "Jose";
Viste mi solución?
Por eso dije que es impropio, porque en vez de reinventar la rueda simplemente con cambiar el COLLATE de la tabla basta y sobra y no hay que dar tantas vueltas.
Incluso con que añada
COLLATE utf8_general_ci al final de la consulta no necesita hacer el cambio directamente en la tabla.
Saludos