The TLD managing company (Example Verisign for .coms) creates a WHOIS record when a domain is first registered.
The WHOIS records are not deleted to my knowledge so you get the original creation date in the latest WHOIS.
Domains that have not been registered yet do not have a WHOIS file.
Therefore the domain name records are never truly deleted just created for the first time and then changed with new owners.