Handle,
Yes and no to your questions above.
I'm assuming two things...
1. You're using Windows 2000 server for your domain (and using Kerbos V5 and not NTLM for authentication).
2. You're using an IPSec tunnel for your VPN connection (becuase you stated above that you're not using a Windows 2000 VPN server, or PPTP).
Active Directory does require that the computer attempting to access a resource is registered as a computer object for your domain. Actually, what it's looking for is a combination of things. Domain/Username/Password. When you log onto a Win2K machine that's part of a domain, your PC's authentication client creates an encryption key based on your username and password which it caches, and then tries to contact the domain conroller (more accurately the Key Distribution Center or KDC) specified at machine logon, just after boot-up. If it's able to contact a KDC in that domain then an exchange occurs and your machine is issued a "Logon session key". Your client then uses this key for the duration of your logon session (or until the expires) when attempting to access domain resources.
Now, if during the machine logon process it can't reach a KDC, you computer still caches the first encryption key. When you attempt to access a domain resource later, your client again attempts to access the KDC for a "Logon session key". If you machine can't secure a logon session key, the computer you're attempting to access will send a user prompt looking for domain credeintials. (ie. domain/username and password). Which I think is happening for your remote client.
Clear as mud right? Not sure if that answered your question. Post back if it didn't.