Marco,
A forma que eu conheço, é a mesma que você descrever ... pois você cria novamente o objeto computer no AD, porém a senha que é utilizada para o sincronismo da máquina com o AD é diferente ...
O que você pode fazer é tentar sincronizar uma nova senha.
http://support.microsoft.com/kb/260575
Não sei se dará certo ... e também acho que você terá que ir a estação para rodar o Netdom...
Mas ... é uma tentativa.
Espero ter ajudado.
Não deixe de classificar a ou as mensagens como "respondido”, caso tenha ajudado.
Fazendo isso, você estará ajudando outros usuários do Fórum a identificar qual ou quais foram as soluções aplicadas na correção do problema.
Luiz Espínola
MCTS - Windows 2008 Active Directory
MCTS - Windows 2008 Applications Infrastructure
MCTS - Windows 2008 Network Infrastructure
MCSE +Security, MCT, MCDBA, Comptia Security+
IBM CSex, ITIL Foundation, Novell CNA, SCSA Solaris 9, Citrix CCA