Note that running through a dictionary and looking for hashes "near" the domain you're interested in works if the DNS server is nice enough to hand out responses of the above form; unfortunately, this can also be used to find which host names are valid for a domain (host names aren't exactly crypto-strength passwords). At least djb advocates giving out answers of the form "there are no domains with hashes between 0xCAFEBABE and 0xCAFEBAC0" (that is, exactly bracketing the query), in which case you'd need to do something more clever.
Unfortunately, I'm not intimately familiar with DNSSEC. I'd be happy to learn the answer, though; if you find it, could you post it as a response, or, if takes a while, e-mail me? (E-mail in profile.)
[EDIT: improved wording, make it clear that actually sending the whole dictionary to the DNS server is not necessary.]
First, ask the root servers for the authoritative servers for the TLD you are interested in:
The root servers don't know about google.com, but suggest you ask [a-m].gtld-servers.net, which are authoritative for .com. (Other TLDs have other authoritative servers.) So let's ask l.gtld-servers.net: The above is an example of a registered domain ("I don't know about www.google.com, ask ns[1-4].google.com"); if the domain is not registered, it looks like this: Of course, [a-m].gtld-servers.net are run by Verisign, who could use this information for front-running. I'd be very surprised if they did, though. (DNSSEC may make it possible to query for the existence of a name without revealing it to the answering server, but I'm not sure - I'd have to read up on the protocol.)