Domain Account slow to logon outside domain

[HJBPS]

We have a unique problem. We have users with laptops that work perfectly in out domain. When they are outside and they logon using cached credentials, it works fine. As soon as they join another network outside, like a wireless etc for internet, the computer slows down to a crawl.
If they start a VPN to our office at this point, it works perfectly.
Any ideas how to make the laptops work ok without VPN on outside network?

We have them on DHCP, DNS comes in through DHCP, not hard-coded.
Please help. Thanks