Hi Liran,
Based on my research, this problem is likely a misconfiguration on the autodiscover service on the server. The ClientAuthenticationMethod parameter is used by the autodiscover service to tell the client what authentication method to use. If you change
the authetication method manualy, the next time the client contacts he autodiscover service it will be changed to the value set by the ClientAuthenticationMethod parameter. You need to set the ClientauthenticationMethod to NTLM.
Disabled the Outlook-Anywhere on 2 of the non-production CAS servers
Verified that the production servers are having just NTLM-Authentication on the servers
Reference:
http://technet.microsoft.com/en-us/library/dd439374(EXCHG.80).aspx
Since this issue is more likely caused by Exchange site, If you need further assistance on it, I'd recommend you post your question to the Exchange server forum:
https://social.technet.microsoft.com/Forums/office/en-US/home?category=exchangeserver
The reason why we recommend posting appropriately is you will get the most qualified pool of respondents, and other partners who read the forums regularly can either share their knowledge or learn from your interaction with us. Thank you for your understanding.
Steve Fan
TechNet Community Support