Die Replikation von Objektlöschungen wird in den AD DS abweichend zu anderen Verzeichnisaktualisierungen gehandhabt. Wird ein Objekt wie beispielsweise ein Benutzerkonto gelöscht, so wird das Objekt nicht unmittelbar gelöscht. Es wird vielmehr ein Tombstone-Objekt erstellt.
Bei dem Tombstone-Objekt handelt es sich um das ursprüngliche Objekt, für dessen Attribut isDeleted der Wert true festgelegt wurde, und bei dem ein Großteil der verbleibenden Objektattribute gelöscht wurde. Es werden nur wenige Attribute beibehalten, die für die Kennzeichnung des Objekts erforderlich sind, wie beispielsweise die GUID, die SID, SIDHistory und der definierte Name (distinguishedName). Gelöschte Objekte werden im ausgeblendeten Container Gelöschte Objekte gespeichert (CN=Deleted Objects). Jede Verzeichnispartition verfügt über den Container Gelöschte Objekte.
Dieser Tombstone wird dann auf alle weiteren Domänencontroller in der Domäne repliziert. Wenn alle Domänencontroller die Aktualisierung empfangen, werden die am ursprünglichen Objekt vorgenommenen Änderungen auf alle Domänencontroller angewendet. Das Tombstone-Objekt verbleibt für einen festgelegten Zeitraum im der Domänendatenbank. Dieser Zeitraum wird als Tombst one- Abl auf zeit bezeichnet. Nach der standardmäßig auf 180 Tage festgelegten Tombstone-Ablaufzeit löscht jeder Domänencontroller den Tombstone aus seiner Datenbankkopie.Mittels Active-Directory Explorer lässt sich der Container Deleted Objects in der Verzeichnispartition anzeigen. Tombstones bzw. Gelöschte Objecte können z.B. mittels ADRecycleBin ganz einfach wiederhergestellt werden.
Die Tombstone-Ablaufzeit wurde in Windows Server 2008 Active Directory abweichend zu Vorgängerversionen festgelegt. In Windows 2000 und Windows 2003 Active Directory betrug die Tombstone-Ablaufzeit 60 Tage. In Windows 2003 SP1 wurde dieser Wert auf 180 Tage erhöht, dann wurde er jedoch in Windows Server 2003 R2 auf 60 Tage zurückgesetzt.