以前Access2000VBAでの開発でReplace関数にはめられたことを思い出しました。
基本形は Replace(expression, find, replace[, start[, count[, compare]]]) です。
引数は3番目までは必須、以降は省略可能です。
私も素直に3番目まで引数を入れて処理を行っていて動作確認も出来ました(Win2k)。
が、実はWin9Xで半角カタカナを含めた文字に対してReplaceを実行すると
意図しない場所の文字が置き換わってしまうという現象に遭遇しました。

色々試してみたところ、引数の最後、[compare] を省略するのが良くなかったのです。
デフォルトではvbBinaryCompareとなっていてバイナリで比較を行いますが、
半角カタカナがうまく比較されていないようでした。
試みに引数にvbTextCompareと明示してテキストで比較を行ったところ
環境に関係なく正常に動作しました。
気付くまで2時間かかりました。。。

挙動が怪しいときは省略可能の引数にも注意が必要です。
その前に色んな環境で試してみる必要もありそうです。
そう考えるとVirtual PCは良いかもしれませんね。