If you're getting the error saying something like "there are currently no logon servers available to service the logon request", here's a potential solution. Logon to the machine with a different user, connect to the VPN, and use the runas command to ping a machine as the user that cannot log in.
I was trying to add a machine to the domain. Also, I was doing this remotely over the internet. I was at the machine, and I added the machine to the domain while I was connected to the VPN. Adding the machine worked, but when I tried to log in with my domain account, that's when I hit this problem.
Now, I vaguely understand what caused this. I was trying to log into Windows, and therefore I was not logged in as any user, and so I was also not connected to the VPN - so there's no way the machine could contact the work machines to request a logon with a domain user account. I needed to do the logon request while connected to the VPN.
So runas logs the user on, and runs the specified command, and of course, it's purpose is to let you run commands as other users. Thus, runas /user:uname@domain "ping somemachine", logs uname into domain and then runs the ping command. If you are able to execute that command, the user will be able to log into the machine, even if you're offline.
You might be wondering why that works. I don't know exactly, but I think the way Windows works is: it caches some information on the local machine that lets the domain user log in for a while without contacting the logon server. I don't know how long the cached info lasts, but I think it lasts for a few weeks by default. And I'm sure there's some way to configure that in Active Directory.
PS - I got these results on Windows 7 (x64) hitting a Server 2008 based Active Directory. Not too sure the AD settings, but as anyone familiar with AD knows, there's a ton of settings that effect stuff like this.