On the problem machines, go to Outlook, Tools, Account Settings, Change, More Settings, Connection tab, be sure the Outlook Anywhere Connect to Microsoft Exchange using HTTP is disabled (unless you have Outlook Anywhere enabled). If you have OA enabled, click the Exchange Proxy settings button and be sure there are ticks in both On fast(slow) networks, connect using HTTP first, then connect using TCP/IP.
I have run into this situation before. As odd as it sounds, the problem was related to a corrupt OST file on the client computer. I was able to fix the problem by disabling Outlook Cached Mode, waiting a couple of days, and re-enabling it.