This reply will NOT fix the problem, it will however, give you some additional information to do so. It looks from your problem description like some network diagnostics are in order.
Get a copy of wireshark (formerly known as ethereal) from www.wireshark.org and install it on one of the problem machines. Make sure you also get the winpcap package as well.
You do NOT need extensive protocol experience for this one – you’ll most likely just be looking at the summary.
Start wireshark on the affected machine, and then select the active network interface from the Capture menu.
Go run Outlook and test for the problem USING THE POP Protocol. Once it has occurred, then stop the Wireshark capture (Capture -> Stop).
Go back to wireshark and browse down the list for the POP login, password and server response.
Hopefully, you will see in this list some indication of the base problem.
Write back with whatever you find.