How to reject at SMTP time without enabling dictionary scanning

One claimed problem with rejecting unknown local addresses at SMTP time is that it enables a spammer to do a cheap dictionary scan of your domain to find valid usernames; all they have to do is try a bunch of RCPT TOs and see which ones get accepted (or don't get a permanent failure). The easiest way around this is simple: just do your greylisting before you give permanent rejections.

This doesn't completely block dictionary scanning (or other versions of address scanning), but it does force the spammer to do significantly more work. Their scanner now needs to be a multi-pass system that keeps a database, retries periodically, and so on. And it takes them longer to scan your domain (especially if you extend the overall greylisting time when mail sources try to hit a significant number of nonexistent users).

If you want to make it more difficult (or can't do greylisting for whatever reason), only give your rejections after you see the message body. However, in this case you'll need to come up with some way of correctly handling messages to a mixture of good and bad local addresses.

Sidebar: the mixed address problem

The problem comes up because your reply to the message body applies to all of the recipient addresses. If some of them are good but some of them are bad, there is no single reply that can be correct; both accepting and rejecting the message is lying about some destinations. You need to somehow contrive that you only accept recipient addresses of a single type, ideally without giving too much information away to a dictionary scanner.

One obvious solution is to keep track of what sort of destination addresses you've seen so far during the RCPT TO processing. When the type changes (when you see the first bad address after good ones, or the first good address after bad ones), you immediately give 4xx temporary failures for it and all future RCPT TOs. Proper mailers will apply the result of the actual message delivery (whether acceptance or rejection) to only the addresses you actually accepted, and retry the other RCPT TOs later.

(You can accept all RCPT TOs for the same type of address, so if the first destination address is a bad one all good ones get a 4xx and all bad ones are accepted (and vice versa if the first one was a good address), but this risks leaking information to a clever dictionary scanner that can notice this pattern.)