So here is how to loose a server off the domain without even touching it.

1. Grab any old machine (or VM in my case) that is in a WORKGROUP and give it a name the same as a machine on the domain.  Reboot.
2. Rename the machine but dont reboot.
3. Join the machine to a new workgroup but dont reboot.
4. Join the machine to the domain.
5. Bingo!  The real machine with the old name will be removed from the domain!  Cool eh?

In my case this was bad.  VERY bad as the VM in question had the same name as our TFS server.  After joining the newly named VM to the domain our devs started whining about TFS being down.  There was a brief OMG moment.  But then it got worse when we found that the local machine account password wouldn't work.  To cut a long story short, phycially disconnecting the server from the network allowed us to login with my domain account (using cached credentials) and from there we were able to rejoin the machine to the domain.

Phew!