I have been experincing the same problem. I still have problems but I am "Half" way there. I had two remote VPN offices, could not browse or join domain from across WAN.
I had some W98 clients and some W2K clients. After the creation of a WINS server, I statically entered the WINS and DNS settings in users across VPN, saw that they were registering with the WINS server..and now they are able to browse.
As for the W2K clients. I had them in the same workgroup as my Domain here. I could see that they were also registering with WINS on this side, but they could not browse. I was able to have them join domain from across VPN WAN (before WINS I could not) and now they too can browse this network.
So I would suggest a WINS server, make sure it points to itself and check to see if clients can reach it (NBTSTAT).
I would suggest, and from what I have read, do not put it on the DC if possible. Also, check the setting on their NIC's for NetBIOS.
Now the last part of my puzzle is I have 2 VPN offices.1 is running fine and can browse. The other cannot. Even though I can see they are beinging authenicated ny DC, reaching WINS and DNS, but just can't browse.
I will keep looking