Cisco Unity Connection Single Inbox 401 Authentication Errors - Windows Authentication and NTLM

After setting up a new Unity Connection 9 cluster to integrate with Exchange 2010, I ran into an issue with the authentication failures when running the test on individual Unified Messaging Accounts.  Running the test against the Unified Messaging Service passed, but this typically only verifies basic network access, domain name resolution and access to the Exchange EWS interface.  The Single Inbox feature will fail if the users' Unified Messaging Accounts can't authenticate to Exchange.

The "Unified Messaging Guide for Cisco Unity Connection Release 9.x" integration guide is quite good and covers about all the scenarios I've ever run into. Follow the guide, and all of the guide, and you should be in good shape.

Following that during a pretty typical setup (a single Exchange 2010 CAS server and another 2010 mailbox server with no DAG), I had an issue where testing the Unified Messaging Accounts failed with a "Failed accessing xxx@ayz.com Diagnostic=[] Verb =[] url=[] request=[] response[]" message.  It is a 401 error, pointing to basic authentication against Exchange issues.

Basic troubleshooting steps, found in just about every Unity Connection gude are:

Check the authentication method on both sides. Check settings in Internet Information Services (IIS) for both AutoDiscover and EWS.
- This was confirmed to be NTLM and HTTPS, under both EWS and Autodiscovery

Try different UM messaging account name formats (i.e. NAME, DOMAIN\NAME, NAME@DOMAIN).
- Tried every combination of names
Reset the UM messaging account password, and enter the password again on Unity Connection.
- Verified name and password via OWA
The UM account should not have a mailbox.
- Verified no Exchange mailbox with admin.
- Another nice method to confirm this again using OWA to check the username and password above.  You should be returned an error indicating there is no mailbox for the user.

Ultimately the issue was that assumptions were made that since Windows Authentication was enabled in Exchange in the EWS and Autodiscovery areas, that NTLM was enabled. The names are commonly interchangeable, but if you are not savvy in Microsoft technologies you may not realize NTLM is technically just a provider available under Windows Authentication.

The fix: Once you find Windows Authentication is enabled, you need to verify NTLM is added as a provider under Windows Authentication.

After losing hours checking and rechecking settings in Unity Connection, grepping Unity Connection logs for anything telling beyond the 401 error, rechecking Exchange settings and the service profile user roles, and furious Googling, my only consolation is that there appears to be an abundance of confusion by Exchange admins regarding this topic and how to effectively set it up in various scenarios.

FYI, while bashing around in Exchange looking for clues, we found some errors that look rather concerning.  Microsoft indicates those are "expected behavior".

Nice.