É uma dor de cabeça notória fazer isso no MySQL, infelizmente.
Consulte O MySQL pode substituir vários caracteres?
Tente isto:
ORDER BY replace(replace(phrase,'¿',''),'¡','')
para remover a pontuação do prefixo do idioma espanhol de suas frases conforme elas são classificadas. Alguém gostaria que o MySQL tivesse uma função REGEXP_REPLACE.
Quanto ao desempenho, você deve estar bem com as funções ORDER BY, a menos que tenha zilhões de frases. Dezenas, sem problemas.
