As far as I can tell, the trick is building up that initial reputation and doing as much mitigation as possible up front: checking for MX records, rate limiting, soft-failing with CAPTCHAs for things that look suspicious, etc.
I know what I'll be hacking on for the rest of the week. :)