I feel like I'm stating the obvious, but if this works from system A, but fails on system B, then the first thing to check would be that things are exactly the same between the two systems. Ensure the scripts are identical, ensure the modules being used are identical. And by this I literally mean identical, I don't mean the same number of bytes, or the same stated module versions. Basically ensure the whole stack is the same.

Do you use Authen::NTLM via LWP or one of the SharePoint modules? Was Authen::NTLM on server A modified? Perhaps to patch the authentication packet for IIS6 & 7?

If the perl code (including all modules used) is exactly the same, then perhaps using a tool like Wireshark would help pinpoint what's going wrong. Compare the same test being sent from Server A and Server B. This may help you back track the issue.

Update: fixed typo, added some text.

Update 2: s/NTML/NTLM/ thanks Corion ;)