Quoting James Fidell james@cloud9.co.uk:
It's sorely tempting to set up a lowest-priority MX that either points to 127.0.0.1, or to a machine that has a daemon on port 25 just returning 4xx SMTP errors in response to every connection.
While it might be tempting, you'll end up loosing some legitimate email. You might also end up being automatically blacklisted by some sites. Some sites block domains that have 127.0.0.1 in MX list. Sometimes, MX lookup on domain part of sender's address in viruses and spam returns a name that when resolved points to 127.0.0.1. Intention is that if bounce is generated, it goes to the local account. Mail servers are way too often configured to include copy of original email in the bounce. Since bounce is generated locally it might bypass spam/virus checks. Sneeky, eh.
I've also seen MTA implementations that don't really care about priorities, they simply connect to the first MX that DNS query returned. It's broken all right, but that's how the things are.
Even with just the "standard" greylisting (no 127.0.0.1 or always return 4xx on lowest priority MX tricks), you'll get in trouble from time to time. I'm not talking about delivery delays (that can be longer than one hour in worst case).
The Symantec Antivirus for Mail Gateways (at least some versions of it) generates warning email back to the sender when it gets 4xx. Rather annoying to the senders that happen to work at places that have it deployed on the border.
Some mail servers (not sure if it's MTA itself or misconfiguration on the admin part though) treat 4xx same as 5xx. No retries, they bounce mail right away.
Some sites have server farms for outgoing mail. If you greylist only on sender/recipient pair, no big deal. If you greylist on sender/recipient/IP triplet, some emails will never pass greylisting since connection comes from different IP address every time. Most greylisting implementations that check the triplet come with whitelisting support and predefined lists of some well known big sites that have farms for outgoing email. But you can always hit some not on the list. I've got bit by that some time ago when I was experimenting with greylisting on my personal domain.
In short, while greylisting reduces spam significantly, be prepared that it's not trouble-free solution. Be prepared to implement workarounds for troublesome sites (boils down to some sort of whitelisting). Your users don't care that MTA on the sender's side is broken. They want to exchange emails, and the intial delay introduced by greylisting is already annoying enough for them (for some even more annoying than spam).
As more sites implement greylisting, spammers are more likely to start retrying addresses they got 4xx. I already see more and more spammers doing this. This makes gerylisting a "temporary solution" that works now. In future it will be less and less effective.
It's the same thing as with SPF/CallerID/DomainKey. Analysis shows that even today volume of spam that fails SPF/CallerID/DomainKey checks is about the same as volume of spam that pass those checks (actually, those checks are not designed to detect or block spam, they are designed to attempt to prevent others to use your domain name in faked email addresses). With domains being sold for around $10/year, I don't see much use of forcing spammers to use their own domain though (so we can blacklist them). The trouble with "allow unless explicitly denied" approach is that it doesn't really work. It's the truth you'll find in chapter one of any book on security. Spammers can easilly use fresh new domain for each single mass mailing. It will only bring the increased revenue to domain registrars (and we'll see number of entries in com/net/org zones on top-level DNS servers exploding).
Want to start new domain registrar business? Now might be a good time. If this SPF/CallerID/DomainKey thing becomes widespread, you'll get your share from spammers profits (as they will be forced to buy new domains at least on monthly basis, if not more often).
Spam is a multi-billion dollar business. Regardless of which side of the fence you sit.