I don't know if it still does it, but mailinator used to have a neat feature where it would "detect" bots trying to scrape its list of domains and start injecting legit ones like hotmail.com/gmail.com
This is probably much more difficult and taxing. On every signup, you're now checking MX records and IP's, not just looking at a string. And Mailinator can change this information regularly too if they choose.
well for one you also need to blacklist the aliases, ex. guerillaclick+sdf@gmail.com, and i suspect sysadmins start showing more hesitation when you need to start pattern matching (risk of false positives and additional overhead)