NOTE: To configure the tombstone lifetime, see tip 3512.
Microsoft Knowledge Base Article 258310 contains the following summary:
When an Active Directory object is deleted, a small portion of the object remains for a specified period of time so that other domain controllers that are replicating changes will become aware of the deletion. This period of time is referred to as the "tombstone lifetime" and is configurable. This article describes how to view the objects that have been deleted.