Win XP Updates

Everyone at one of our clients branches cant run windows updates, even under administrator. Windows scans for updates, start downloading it and then gives up half way and says unable to do updates. However, if the laptop users tries this from home, logging on to their domain via vpn, they can actually do this. Now I have checked with the guys who supplies the network, there is no restrictions on the proxy they use. You can however go to microsoft’s website, select a hotfix file, download and install it, no problem. What is going on here? Any ideas?