Para o seu domínio de 2003, use uma ferramenta como o > Administrador LDAP do Softerra para visualizar e recuperar itens excluídos do Active Directory.
Você precisaria de um controlador de domínio do Windows Server 2008 ou mais recente para usar o PowerShell para essa consulta. Aumentar o nível funcional do domínio para 2008 também permite ativar um novo recurso da Lixeira do Active Directory.