I'm guessing zone files. If you load zone files into something quick to search like an indexed DB table, memcache, etc they are super fast. They are also inaccurate and give you false positives since a domain can be out of the zone for a multitude of reasons.
You can do the initial search in the zone file and then if it doesn't appear there you hit the Verisign registry whois (for .com and .net). The amount of times the domain doesn't appear in the zone file is nominal.
