You could first try the ANY query (which won't return all records though) and then a whois query on failed ones to be sure. Combined with some smart caching and

You could first try the ANY query (which won't return all records though) and then a whois query on failed ones to be sure. Combined with some smart caching and affiliate/click tracking (to see if a new domain gets registered).