Heh.

Okay, something to know: The computer's name is inexorably linked to that security trust relationship I mentioned. If the trust happened to get broken (and there's a few different ways that could have happened, including if you imaged the drive and restored the image), then you will never be able to join the computer to the domain as long as it still has that name.

You might want to try renaming the computer to a previously-unused name, and then when you try to rejoin the domain, give it your domain administrator password in the box you mentioned.