You need to look into a third party application for remote desktop support with Windows. We use LANDesk where I work and of everything I've used it is really nice. Regardless of what you choose to do you are going to have to touch each computer, whether it's to have the computer log into the new domain you've just set up, or to install a piece of client-side software that will allow you to remote control that computer.
www.landesk.com
VNC is nice in that it is simple, but allows you no feedback, it just sits there and you can't find out that computer's name or IP address without you knowing it first.