Calls made to the UM enabled user would go to voicemail, the greeting would play, and the caller could record a voicemail, but the voicemail would not be delivered to the UM user's mailbox. We turned up UM logging using the following cmdlet:
Get-EventLogLevel "msexchange unified*" | Set-EventLogLevel -Level ExpertAnother voicemail test showed the following MSExchange Unified Messaging event ID 1423 - A TLS API failure occurred. Error = 0x80090331.
A quick look in the %ExchangeInstallPath%\UnifiedMessaging\voicemail folder on the mailbox server hosting the UM user's mailbox showed all the voicemail WAV files queued for delivery.
I'm familiar with error code 0x80090301 on this event ID, which is caused by too many root certificates in the Trusted Root Certification Authorities store, but this code and error sting is different. 0x8009331 means, "SEC_E_ALGORITHM_MISMATCH - The client and server cannot communicate, because they do not possess a common algorithm." Definitely sounds like a TLS negotiation problem.
After double-checking the UM configuration and the SSL certificate configuration used by the UM services it was found that TLS 1.0 was disabled for clients on the Exchange 2013 servers. The registry key HKLM\SYSTEM\CurrentControlSet\Control\SecurityProviders\SCHANNEL\Protocols\TLS 1.0\Client\DisabledByDefault was set to 1. This key doesn't exist by default and was not being configured via GPO, so it must have been configured in their server build. Setting the value to 0 (or deleting the DisabledByDefault key) fixed the problem.
The problem occurred because the UM server acts as both a client and a server to itself. The UM service acts as a client when it reads the voicemail WAV files from the voicemail folder and uses TLS to do so.
Note that there were several improvements to TLS and SSL in Exchange 2013 CU8 and Exchange 2010 SP3 RU9. These versions support TLS 1.1 and 1.2, which should also work. Please read Scott Landry's excellent article, Exchange TLS & SSL Best Practices, for more information.