Há algum tempo escrevi um post contendo um exemplo de método para fazer replace em toda String. No caso o método que escrevi usava while e realmente é muito menos eficiente do que as alternativas apresentadas nos comentários, a primeira usando Expressão Regular (sugerida pelo Almir Mendes) e a segunda utilizando split e join (sugerida pelo Lucas Ferreira).  Então resolvi (depois de muito tempo) fazer um benchmark utilizando os três métodos para poder chegar a uma conclusão sobre qual seria melhor.

Fiquei muito surpreso com os testes, não porque o método utilizando while foi de longe o pior entre os três, mas sim pelo fato do método que consiste em dividir a String em um vetor e depois junta-la novamente (split+join) ter sido mais rápido do que o próprio método de replace do javascript utilizando Expressão Regular (já que o split também utiliza ER).

Outro fato interessante é que tanto utilizando ER quanto split-join os métodos se mostraram bastante escaláveis, enquanto o com while piora consideravelmente conforme o número de ocorrência aumenta.

Lembrando que fiz os testes através desta página que criei utilizando como browser o Firefox 3.0.5. Caso alguém faça os testes e obtenha resultados diferente gostaria de receber feedbacks.