Did you find an answer to your problem? I am having the same trouble. I have two XP SP2 workstations that were bound to our old OS X 10.3 server. We setup a new Xserve with 10.4.6 after taking down the old server. We are using the same domain.
I can’t seem to get the Windows clients to rebind to the new server. I have removed them from the domain, and made them part of a workgroup. Changed the workgroup to something other than the given domain/workgroup. Shut down the computers. Restarted without ethernet connection. Rebound them, with apparent success, but every time I try to log in, I get an error the that domain “is not available.”