Então, dois controladores de domínio virtuais ... são ambos servidores DHCP? Parece que apenas um é. Nesse caso, ficaria tentado a executar algumas semanas com o servidor DHCP usando apenas o outro controlador de domínio como DNS. E depois por algumas semanas com o outro controlador de domínio desligado.
Você sempre pode reverter a alteração se ela afetar os usuários, mas isso pode ajudar a diminuir a caixa (se for apenas uma) que está causando o problema.
Eu também ficaria tentado a adicionar um terceiro DC e, em seguida, descomissionar o segundo para descartar a possibilidade de alguma estranha corrupção de instalação do tipo que o Windows adora usar.
Você tentou reiniciar os serviços no DC em vez de reinicializá-lo?
Os DCs hospedam outros serviços (arquivo, troca, etc)? Como você tem um ambiente virtualizado, você tem espaço para mover esses serviços para seus próprios servidores por algumas semanas para descartar a confusão desses papéis?
Além disso, e como não foi comentado, com relação ao erro "Não há armazenamento suficiente para concluir esta operação". Se os discos do servidor estiverem cheios, todas as suas funções DC começarão a falhar. Os discos estão cheios?