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? Or is this the same situation that you're already in (except you added it a long time ago) and it's not working?