Domaintools is the only service I know of, I very much doubt they would get every name though. There was a company a few years with something along the same lines but not as good, I can't remember the name, was something "ip" and aimed at the legal market. They charged a fee for full lists but some of it was free.
To get a complete list would be very difficult because they'd need to do whois lookup on every single name in the zone file (not sure it .com.au even publishes one).
It is a lot easier though if someone uses their own nameservers.