Note that @mailinator.com email addresses are blocked at a significant number of sites due to its popularity. Throwaway email sites that alternate between several different domains work best.
Instead, the site will randomly show one of the alternate domains on every page load. At one point, it would even give 'gmail.com' and other legitimate domains as the alternate if you tried to scrape them too quickly (or rather, they hypothetically-yet-definitely-didn't-do that).[1]
Today, the alternate domains are shown as an image[2], and even that isn't a complete list, since other people can simply redirect mail incoming to their domains to mailinator.com. Mailinator explicitly condones this.[3]
[1] http://mailinator.blogspot.ca/2011/05/how-to-get-gmailcom-ba...
[2] http://www.mailinator.com/get_alt_domain
[3] http://mailinator.blogspot.ca/2007/10/new-mailinator-alterna... (end of second paragraph)
Resolving not-mailinator.whatever.com returns:
not-mailinator.whatever.com. 86400 IN MX 10 a.bad-mailserver.com
not-mailinator.whatever.com. 86400 IN MX 10 b.bad-mailserver.com
not-mailinator.whatever.com. 86400 IN MX 10 c.bad-mailserver.com
not-mailinator.whatever.com. 86400 IN MX 10 d.bad-mailserver.com
not-mailinator.whatever.com. 86400 IN MX 10 e.bad-mailserver.com
not-mailinator.whatever.com. 86400 IN MX 10 f.bad-mailserver.com
not-mailinator.whatever.com. 86400 IN MX 10 g.bad-mailserver.com
not-mailinator.whatever.com. 86400 IN MX 10 h.bad-mailserver.com
not-mailinator.whatever.com. 86400 IN MX 10 mailinator.com
You could put a limit on the number of MX records a domain can have, but Gmail has 5 and so you'd only reduce the chance of success to 80%.
Then you have to consider the mechanics of DNS. How many layers of CNAME indirection will you follow? Will you cache results? (If so, how will you trust that the responses are valid?) How long will you wait for DNS responses?
A poor implementation of DNS lookups will use unbounded time, unbounded bandwidth, and unbounded file descriptors. This isn't a hack you are going to code up in an afternoon, and one mistake means your website is going to randomly go down.
And so you have to ask: why? Why do you care if someone uses mailinator? Spammers are just going to set up their own domain or use someone's malware'd Windows box. And someone that wants to ignore your email is just going to have a procmail rule auto-submit your messages to Spamcop anyway.
So you gain nothing, spend a lot of time programming, and it won't solve any problems. In conclusion: worst idea ever.
(I'm not trying to block Mailinator, just some exercise for myself.)