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 firstname.lastname@example.org 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
- 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".