Also, do you have any experience with unreliable VBA with Office 2003? This macro seems to perform a lot better on Office 2013.
as i am still using an earlier version of outlook, it is hard to be certain what version incompatibilties there may be, but replace is a basic vba function and should work correctly in all versions
i have just retested your code above and it works for me, to replace ### with a numeric string