Supongo, por el código y por el hecho de decir que solo te remplaza una vez, que no estas usando vbscript.
Por default, replace de vbscript hace todas las sustituciones posibles si así se lo indicas, basta con
revisar la ayuda de este comando.
Código:
<%
cadena = "Este es un texto largo<br>como podría ser cualquiera,<br>es simplemente para probar<br>una función"
response.write "<textarea cols=40 rows=3>" & cadena & "</textarea>"
cadena = replace(cadena, "<br>", VbCrLf)
response.write "<textarea cols=40 rows=3>" & cadena & "</textarea>"
cadena = replace(cadena, VbCrLf, "<br>")
response.write "<textarea cols=40 rows=3>" & cadena & "</textarea>"
%>
Como puedes verificar, el segundo TEXTAREA sale como deseas con solo un replace.
Saludos