At $work, I installed Microsoft's Firewall Client for ISA Server. With it running, my non-MS applications (like, say, LWP) manage to authenticate themselves to the proxy and talk to the Internet.
Without the client, my symptoms were different from yours. I got 407 errors from the proxy - not 404s. Perhaps you have something else going on.
Can you talk to the Internet at all from your applications (outside of Microsoft applications)? If you can get LWP installed "by hand", can you use lwp-request to fetch Google's homepage? That would be how I'd start to narrow the problem down.