Re-wrote a system for a company that processes legal invoices - the original system was a VB monstrosity that had no idea of good OO principles - everything was mixed together. The HTML did SQL, and the SQL wrote HTML. A large part of it was a custom rules engine that used something like XML for the rules.
Two teams did the re-write, which took about 9 months. One team did the web front end and the backend workflow, while the other team (that I was on) re-wrote the rules engine. The new system was written in C#, and was done test-first. Adding new rules to the system when we were done was dirt simple, and it was all testable. Along the way we did things like convert the company from VSS to SVN, implement continuous integration, automate the deployment, and teach the other developers how to do TDD and other Scrum/XP practices.
Managing expectations was crucial through the project. Having a customer that was savvy about software was very helpful.
Having a mix of large scale (end-to-end) tests along with comprehensive unit and integration tests helped tons.