I have found several domains on the internet that have no nameservers, however they have WHOIS records and domain registrars say they are taken.
My understanding of DNS on the internet was that the presence of a domain's nameserver showed that is was registered, but apparently this is incorrect.
So, how can a domain not have a nameserver, and what determines if a domain is available or not? WHOIS?
The only way to determine if a domain is available or not is to query the registry database for that domain. Usually you can do that by performing a WHOIS query on the registry WHOIS interface.
There are several reasons to explain why a DNS check is not safe.
The most simple explanation is because you can register a domain without pointing it to any location. It's like a house. You can buy a house, but you are not forced to build a road to reach it.
The most part of available domain providers force you to point a DNS, otherwise they set a default one. But you're not forced, it's not a kind of mandatory domain requirement.
The second reason is because there are actually cases when a domain is registered but not available. One of this cases is the period often known as redemption period. This period lasts for some days after the domain is expired and the current owner don't renew it. Several registries disable the domain, it means it is no longer reachable via DNS, but the domain still exists and can be redeemed (usually) only by the original owner.
The DNS check is cheap and sometimes faster. If you need to check whether the domain exists, then you can try a DNS query first and, in case of failure, fallback to the WHOIS query. In other words, if the DNS query succeed the WHOIS query is almost pointless. But you cannot do the opposite because if a DNS query fails, it doesn't mean the domain is not registered.
Yes, you are incorrect. A domain is only available if it has not been registered; that it is not available via DNS does not indicate that it has not been registered, merely that it is not able to be looked up on the Internet.
This stack overflow question gives more useful details on the whole process.
As stated in this StackOverflow question "Checking domain name availability with DNS records" registrar databases are the only definitive way to determine if a domain name is owned or not. DNS is only necessary if you plan on making your domain resolvable.
(Answer stolen, with permission, from Zoredache's comment as per this Meta thread.)
Whois records are only valid for some domains, usually delegations from some TLDs (including odd ones like *.co.uk.), where some registrars handle the administrative tasks of delegating subdomains.
So technically, you are right: a domain is free if there is no delegation and no resource: it is not in use.
On the administrative side, whois records are the most convenient way to go, but lots of rules may apply: some names may be judged as offensive, some TLDs are reserved to some countries, ... even if whois records say the domain is free.
Some domains operate without any registrars nor whois records: eu.org is a good example.