Evolving our mail system step 1: adding an external mail gateway
The first change we made in the evolution of our mail system was to add a separate machine to be our external mail gateway, putting it in front of our central mail machine for outside email. We did this for two reasons: first, we wanted to introduce some sort of system-wide anti-spam features, and second, the central mail machine was heavily overloaded by directly handling external email (partly because it had a very old MTA that had an unfortunately heavyweight way of handling incoming connections and partly because it was on a very old and small machine).
Shifting the work of handling mail from the outside world to a separate machine meant that we could have a modern mailer (on modern hardware and a modern operating system) deal with all of the difficult and troublesome parts of taking email from the outside world; talking to the hordes of spam zombies, rejecting bad local addresses, and so on. It also gave us an obvious and simple place to add mail filtering, one where we didn't have to change our existing central mail machine.
In the abstract, this is a simple change; we just had to build a machine with suitable spam identification, configure it to forward all email to the central mail machine, and make it accept only valid local addresses. And this is what made life interesting, because our central mail machine was a black-box mailer configuration, so the first thing we had to do was reverse engineer enough of our existing mailer configuration so we could create a white-box mailer setup.
Once this reverse engineering had been done, we built (and tested) the actual machine and mailer configuration. We selected Ubuntu as the operating system (because we already knew we were going to move to Ubuntu Linux in general) and used Exim as the MTA (see here for why). I didn't try to fit our configuration into the whole Debian/Ubuntu 'split' Exim configuration; instead I started with the single-file Ubuntu Exim configuration and rewrote things from there, engineering in the checks and anti-spam things that we needed.
In the process of both the reverse engineering and setting up the machine, we wound up making a lot of decisions about how we'd manage our new Ubuntu Linux machines, because this was the first such machine. In turn, this required building a certain amount of infrastructure.
The actual deployment was simple; we changed MX entries from the central mail server to the new external mail gateway. We started with a few less used domains and hosts, as a final precaution that hopefully shouldn't lose too much email if something exploded, and once that went fine we made the mass change of all of our MX entries. In the process we learned some things about the limits of bridging NAT and annoying spammer behavior; in the end we had to firewall off the old central mail machine from the outside world in order to force spammers to stop talking to it.
The change had positive effects right from the start. We noticed the much smaller load on our central mail machine (which meant that it processed email much more promptly); users noticed the spam tagging we had introduced and had immediate, positive reactions to it. Overall it was a great and much-needed success that got our users to feel much more positive about our email system.