Why don't you just terminal serve into the machine and add the machine to the domain that way.

Because (a) I shouldn't have to, and (b) that is almost as much trouble as having to walk up to the machine and futz with it. I should be able to pre-add a computer name to the domain and then not worry about the exact time and place that user decides to actually connect it up.

Which brings me to Bitt's point...

I am totally not a Windows admin, but can't you add a computer to the domain from the domain controller itself, essentially pre-registering it, and then when it tries, it gets in?

That's exactly what I'm talking about, Bitt. That procedure you just described worked on Windows NT and Windows 2000. But the feature that allowed it to work is flat-out missing from XP. In the place where it would have allowed you to just connect the pre-registered computer to the domain, it now forces the user to add the computer to the domain with an administrator's username and password, instead of just allowing it to use a pre-existing one. That's the exact crux of the problem.

The problem happens whether I'm adding a new computer to the domain, or the user has switched from domain to workgroup and back again. Same screen, same problem.