We recently had a rash of spam sending due to someone finding, guessing, or leaking a user's password. Sometimes, it just requires that, not some security breach. Well, we didn't catch it and stop it in time, and now we're suffering some deliverability problems ranging from slowdowns to outright blocking by some servers.
What I've learned, aside from the importance of being proactive, and maybe even running spamassassin on outgoing mail, is that a few email providers are clamping down on spam by blocking servers, or downgrading the deliverability of some servers.
Some of these companies are Gmail, Yahoo, AOL and Microsoft. These companies dominate the web-based email, and represent the majority of email on the network.
I don't know the details, but there are a number of things which help deliverability, ranging from easy to hard, cheap to expensive. This article will be revised with things I'm doing to improve deliverability. In no particular order.
Sender Policy Framework (SPF)
This is a TXT (text) record in a domains DNS that lists what servers are allowed to send mail for the domain. The simplest is to use "a mx ~all", which means "the parent domain, and any domains in the MX record, and nobody else". The SPF syntax is simple. Here's what it looks like in BIND:
example.com. IN TXT "v=spf1 a mx ~all"
And how it looks in djbdns/tinydns:
'example.com:v=spf1 a mx ~all:::
In tinydns, you need to escape the : with \072 (octal 072), because : is a delimiter.
'example.com:v=spf1 a mx ip4\07220.127.116.11 ~all:::
This is mainly for Google and Yahoo at this time. You publish a public key and then sign all your email with the private key. (This would not have prevented our spam problem.)
Test all the mail accounts for weak passwords using John The Ripper. This was our security hole - a guessable password. This is the same problem facing the big guys.
Test Outgoing Mail
Try running all the outgoing mail through Spamassassin, and record the stats. I didn't crunch numbers, but looked at logs, and it appeared that we had a mail script on a website that was being used to send spam. Since mail forms still exist, I decided to write a wrapper for /usr/lib/sendmail that would log and whitelist scripts to run sendmail, and scan the outgoing message. Thus, only "legit" scripts could send. Even though those were being exploited, the message could be checked to see that it was sending to the correct email address.
Inbound Email Issues
[Updated 2016] For a few years, we were using an inbound greylister, and it worked great, except that incoming mail took forever, and I think we lost some messages. I don't know if a spam blocker helps, but it should prevent "reflection" spam, where a message is sent to a bad address, so that the email software rejects it and bounces it back to the sender. The sender has been forged, so the email routes to this forged sender, who then reads the bounce message.