O comando que eu corri realmente funcionou, levou apenas alguns minutos para que ele tenha efeito por algum motivo.
netdom resetpwd /s:server.company.lab /ud:na\domainAdminId /pd:password
Não sei porquê. Acho que alguém estava reiniciando alguns dos servidores do AD no momento em que executei o comando, o que poderia ter jogado fora.