I've experienced (oh, have I experienced . . . *grumble*) problems with a proxy server running on NT in that it expects to receive NTLM credentials but after an unsuccessful round of expecting that will fallback to accepting Basic authentication instead. That's another thing to get with your proxy administrator about (along with getting them to look in the logs as was previously mentioned).

And no, I don't have a workaround for the problem in Perl; fortunately in my case there was another proxy that didn't require NTLM available. We did investigate some sort of NTLM proxy (a proxy proxy that provides the real proxy with the NTLM credentials it wants), but I wasn't involved in that part so I can't give you more than that vague pointer.