If you were having problems with clients prior to XP, I would guess that for whatever reason TCP/IP was not bound to the VPN connection. In theory this should not be possible as TCP/IP is bound to every connection with XP. You don't have a major problem with the TCP/IP stack, or you wouldn't have any connection at all. I also get the impression that you have multiple XP clients with this problem.
Having said that, other protocols being present on the server side but not on the client side can in certain combinations cause this error, so check to make sure the protocols bound on the server side are also bound on the client side. If for some reason TCP/IP is not bound on the server side you would see this problem as well.
Also, there were problems with ppp in W2K, particualy prior to SP2. Make sure you are up to date with those service packs on both sides.
Failing that, enable logging on the server side and see if anything of interest shows up there. If nothing there, I would enable logging on the client side and check that out. Both sides should show something, but at least one side will for sure. Doesn't really matter which side you start with, I usually start with the server because it is a little easier start to finish and I'm lazy. Instructions here:
The article mentions it, but make sure to disable logging when your done as it does eat hard drive space. Also, the article doesn't mention XP, but the netsh instructions for W2K Pro should work.
If you see something there you don't understand, post back.