When DNS records are deleted from AD integrated zones, they are not immediately tombstoned in the way normal AD object deletions are. Instead, they go through a DNS tombstone process. This includes setting dnsTombstoned=True for the object.
When set to True, the DNS console and tools will ignore the presence of the record. You will still see the objects through LDP/ADSIEDIT/LDIFDE alongside the other DNS records. Each DNS server is hard coded to perform a cleanup process every morning at 2 a.m. to delete any dnsTombstoned=True records that are seven days old or older.
It is at this time that the objects are tombstoned like normal AD deletions (isDeleted=True) and moved to the Deleted Objects container. This is important to know in case someone deletes records, such as enabling scavenging for the first time, and wants to know why they still see the objects in Active Directory. The reason for the seven days of dnsTombstoned=True is to prevent frequent database churn. This is because workstation records may get de-registered or scavenged and then re-created within a short period of time.