Not quite what you're asking, but it might be worth talking to your proxy administrator and see if they are willing to make an exception to authentication from a fixed IP address (if you're writing server code).

I have also had success using wget (works under cygwin for windows users, also seems to be available as a native windows binaries) when talking to troublesome proxies. Not as nice as doing it inside Perl, but sometimes you have to go with what works (if you don't have the time to go poking inside TCP packets, as fun as that can be ;)