Qualquer solução utilizando expressão regular vai cair no mesmo problema de ineficiência. No link que @dcastro mencionou existe uma breve explicação sobre isso em inglês. Análise (parsing) de expressão regular é O(n)... Quer dizer, o algoritmo tem que atravessar a String inteira (de tamanho n [e n que pode ser um texto razoavelmente grande]) para realizar a análise. A solução é usar um mapa de caracteres e substituir um por um. Veja a diferença nos gráficos: jsperf.com/diacritics – rdllopes 4/02/14 às 15:57
Como esses caracteres não tem relação relação matemática alguma na tabela unicode. A forma que vejo é fazer a substituição "manualmente", pelo menos usando expressão regular. Dá um trabalho, mas é funcional.