pues teóricamente y según la O'reilly javascript reference el método replace() funciona a partir de NS4
de todas formas... para qué molestarse en un navegador que no compite con ninguno ?? Creo que es hora de dejar de lado las versiones viejas que no respetan los estándares para que los usuarios se decidan de una vez a usar navegadores decentes, lo que hará todo más fácil para todos.
NS4.x tiene como 6 años... eso en un navegador es muchísimo. Y el problema no es que tenga yá tiempo, si no que es una versión que no merece la pena contemplar 6 años más tarde porque la hicieron muy mala.