I ran across a website hosted by the Censys Team at the University of Michigan called the Internet-Wide Scan Data Repository. They scan the entire IPv4 address range regularly, checking out websites, open ports, SSL certificates, etc... for each scan they run they also take the time to do a DNS lookup and store the results as a separate package for download.
Project Sonar includes a regular DNS lookup for all names gathered from the other scan types, such as HTTP data, SSL Certificate names, reverse DNS records, etc
The dataset contains snapshots taken within a timeframe of maximum 8 hours each. New snapshots will be added as additional data is collected. The forward DNS requests are made with record type 'ANY' which results in all kinds of result records being returned. The first upload contained only the following types: A, AAAA, CNAME, MX, NS, PTR, SOA, TXT. Since then we've changed the parsing library (ldns) and are now uploading all records we retrieve, as far parsed as possible. The data might contain unknown record types and known but incorrect ones next to all the different parsed types.
Now I know that this won't be a complete list, but it does include MX records for any domains that were picked up through other scanning means. I extracted the file, ~70GB's unzipped, then ran a parallel grep on it for the mail server in question (Mailinator). I was able to track down ~460 distinct domains that all use the same mail server using this method.