I was working at a site where outlook would continually prompt for the username and password, even when they were entered correctly. If I went into the mail account settings and unticked the "Only connect to proxy servers that have this principal name in their certificate" checkbox, the user would be able to authenticate, but after exiting outlook and re-opening the option was re-enabled, and the certificate name that it was looking for was filled in, which caused problems authenticating again.
The issue was occurring because the exchange server is using a wildcard cert, so the name that outlook was looking for (mail.domain.com) did not match the name in the certificate (*.domain.com).
In order to stop the exchange server from sending the wrong settings to outlook, I issued the following powershell commands:
set-OutlookProvider -id EXPR -server $null
set-OutlookProvider -id EXPR -server $null -CertPrincipleName none
It took a few minutes before outlook started picking up these new settings, but it does appear to have resolved the issues we were seeing.