Did you consider using the gTLD zone files (from the respective registries) and the ccTLD zone files found @ http://viewdns.info/data/? A much bigger initial dataset than 25M domains right there?
Feel free to grab a copy of our domain list. The "All domains with NS records" is the one you want. Has 191 million in it.