I faced a similar challenge. The technique I used was to carefully read the code of the program to be rewritten, and then I wrote a spec for it. The format of the spec was that everything that was feasibly testable was written as a unit test, and everything else was written as comments between the tests and the text explaining them. Naturally the original code satisfied the test suite/specification.

Then I used that test/spec to do a TDD type development of the new service. It was the easiest rollout I've ever done. Everything just worked when it went into production. I even ended up giving some internal presentations on the process.

I also tested with logged input from the source program. It's neat to see this technique is common.