In a scenario where there are 1000+ deleted objects in an Active Directory domain, you may encounter thet the "Deleted Objects" container within the Recovery Manager console and/or the Active Directory Users and Computers tool is empty.
In Recovery Manager for AD open Deleted Objects folder, right click on it and select "Set View Options...". Change the "Maximum number of objects to show" to 1000 or less.
Download and install on the target domain controller the hotfix mentioned in Microsoft Knowledge Base article 977180 "Error message when an application or a service tries to query for any deleted objects by using a well-known GUID in a Windows Server 2008 R2-based domain if paged search is used: '0x8007202c Critical extension is unavailable'". This article is available at http://support.microsoft.com/kb/977180.