Fastest way is to check whether it exists in the nightly zone file, and then a DNS lookup, and whois query.
edit: "Zone file" is the file containing the records of all registered domains in a zone (.com or .net). Last time I checked it was something 80M records for .com