I've found several postings of problems similar to this that were solved with cleaning out the keychain or completely recreating the profile for Outlook - both have been tried on various computers having the problem.  The problem occurs on about 20% of the Macs in our environment.  The timing of the problem did coincide with renewing the 3rd-party certificate on the CAS servers.  We have also removed any existing certificates on the problem Macs without success.  From packet traces, it does appear to have problems with successfully resolving the server from autodiscover - but 80% of the Macs and all of the PC's don't have problems so I'm hesitant to make drastic changes.  The error itself is very generic to being an authentication error and requiring attempts to login repeatedly.

Having a PC background myself, I'm not positive I've referred to everything in the proper terminology - but I hope it is close enough to make my issue understood.

Some Mac OS 10.7, 10.8, and 10.9 are having the issue and others with the same OS are not.  It has been very elusive on discovering the underlying issue.  We are running Exchange 2010 SP3 with RU4.