Microsoft Knowledge Base Article 892806 contains the following summary:
When an Active Directory object is deleted, a small part of the object remains for a specified period in the deleted objects container so that other domain controllers that are replicating changes will become aware of the deletion. By default, the System account and members of the Administrators group only can view the contents of this container. This article describes how to modify the permissions on the deleted objects container.
You may have to modify the permissions on the deleted objects container if the following conditions are true:
• You have enterprise applications or services that bind to Active Directory with a non-System account or a non-Administrator account.
• These enterprise applications or services poll for directory changes.