Over the course of the service lifetime several testing methods were removed or simplified to avoid problems.
Although not all such tests are listed here we hope these will make good examples regardless.
As per the SMTP protocol (See Appendix G for a brief example) clients will identify themselves to a mail-server using the HELO (or EHLO) statement followed by their name.
For a brief space of time we rejected messages from clients which didn't identify themselves with a name which was fully resolvable in DNS. This led to a flood of errors, mistakes, and complaints.
Ultimately we cut back the testing of HELO to only reject messages which came from clients that identified themselves with:
An unqualified hostname. (ie. A name not matching the pattern "/([^.]+)\./")
An IP Address. (ie. Matching the pattern "/^([0-9]+)\.([0-9]+)\.([0-9]+)\.([0-9]+)$/")
*.local, *.lan, or *.internal. (i.e Matching the pattern "/(.*)\.(local|lan|internal)$/"
HELO tests were ultimately very cheap and extremely reliable, once we'd decided upon an appropriate level to perform them at. But they're a perfect example of the difference between a naive anti-SPAM test and something that doesn't make mistakes.
Greylisting is a relatively new anti-SPAM technique which is designed to ensure that mail sent from unintelligent sources isn't accepted. Essentially greylisting replies to the first delivery attempt of an email with a temporary error, on the understanding that a real SMTP server will queue messages which it cannot deliver immediately and retry them in the future.
After the first delivery attempt has been rejected with a temporary error any subsequent delivery attempt will be allowed. This is useful because many SPAM senders only wish to connect to as many hosts as possible to send their content - they don't care about failures, and will not retry if they see an error.
In a typical greylisting implementation three things are locally recorded, and used to keep track of whether an incoming connection should see the temporary error, or be allowed to deliver their mail:
The IP address of the sending host.
The sender's email address.
The recipient's email address.
The reason we found greylisting difficult to implement was because our satellite MX machines were stand-alone, and had no shared state with each other. This meant it was easy to see examples of incoming email being rejected too many times. (For example the mail might be delivered to incoming0.m-s.com, be rejected with a temporary error, and then have the same thing happen with incoming1.m-s.com & incoming2.m-s.com.)
This problem would be exacerbated if the source IP which was sending the mail was constantly changing too. (For example mail sent from an @googlemail.com might be delivered the first time from the host outgoing1.mx.google.com, and the second attempt might come from the unrelated host outgoing2.mx.google.com)
Ultimately we did provide greylisting for users who wanted it, but we only tracked the sender and recipient email address rather than the source IP, and we knew that there was a reasonable chance each mail would require more delivery attempts than expected.
Partly due to these implementation issues, and partly due to the falling effectiveness of the technique itself greylisting was never advertised as a feature to users.
Nolisting is a technique which is related to greylisting, and has seen an interesting rise in popularity.
We chose never to recommend, implement, or endorse this approach however it is an interesting technique which might be useful to some hosts.
You may read the details at http://nolisting.org.
Language rejection seemed like a simple thing to add because we certainly saw a lot of what could be best diagnosed as "foreign SPAM". (That is SPAM mails written entirely in Russian, Chinese, or French languages).
Unfortunately reliably detecting foreign mails was a pretty difficult proposition. The common approaches would be to use either:
Statistical analysis on the text in the message.
Examination of the character/encoding headers contained in the mails (MIME-types).
Unfortunately statistical analysis of character frequency and letter-combinations never appeared to be more than 70% effective, and many legitimate users who were bilingual, or multilingual, would have MIME Content-Type headers that identified themselves as KOI, or big5 - so these headers couldn't be trusted.
So although language detection was possible in theory, and early attempts blocked a lot of foreign SPAM (primarily from Russian and the Far East), the false positive rate was too high for it to remain in use for very long.