Sounds like we should set up a reverse botnet with a rating system, then.
Talk to some other companies you know, create a system that takes a list of failed logs, anonymizes it somewhat and publish it. They do the same, you all have a system that pulls down the list from the others and puts that into a list of "hosts we probably don't want to talk to, because they have tried as email@example.com".
If the lists are properly anonymized and we have a rating system so getting bad data into the system is harder, I think we'll have more or less countered them for now.
I'm sure the next reply will tell us all about somebody who already has this designed and set up.