Se você acessar o console Usuários e Computadores do Active Directory (em Ferramentas Administrativas), poderá selecionar vários usuários em uma única unidade organizacional e excluí-los todos de uma vez:
Isso deve torná-lo muito mais rápido.
(essa imagem foi tirada em uma máquina SBS2011, mas é praticamente a mesma em 2003).