I used to use a telnet based approach to check if the account exists, but most servers these day don't respond with the correct error response if an account does not exist.
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. :)
Yes you need to protect the log in page by rate limiting, Captcha, looking up mx records, etc.
One approach I have thought would be good to use is a rainbow table like approach. Most people are not very imaginative about the fake email accounts they use.
I've been thinking about this space for a while (e.g. https://news.ycombinator.com/item?id=12411204 ) and would be happy to chat or brainstorm.