The first change we made, was to improve our spam handling responsiveness.

We have three servers running spamassassin's spamd, and that wasn't enough to keep up with the 95th percentile of e-mail. Our system was already scalable, but in order to handle tens of thousands of messages in a few minutes we would have to have a LOT more servers than we had.

Rather than throw more servers at the problem, we looked at our logs and identified where our mail was coming from. (See my blog post on the issue.) It turns out that about 50% of our mail is internal and another 35% comes from facebook. Since we authenticate most smtp connections and facebook doesn't send us anything spamassassin would consider spam, we were able to cut our spam handling load by 85% by not spam checking any mail where our servers authenticated the sender or which originates from facebook's ip address range.

As an added bonus, we never get any false positives on internal mail anymore.