We came across an issue recently, where unified message was not working on a Exchange Server. It had all the correct Dial Plans configured and was enabled for Exchange UM.
The Exchange server was integrated with Lync 2010 , whenever we tried to leave a voice mail the following event was logged on the Lync Server.
“An attempt to route to an Exchange UM server failed.
The attempt failed with response code 504: servername.server.com
Request Target: [DialPlan@servername.server.com], Call Id: [gagf564646-c054440e4-bd9yue-0622ebgsafsa2ac].
Failure occurrences: 6, since 15/06/2011 19:56:16.
Cause: An attempt to route to an Exchange UM server failed because the UM server was unable to process the request or did not respond within the allotted time.
Check this server is correctly configured to point to the appropriate Exchange UM server. Also check whether the Exchange UM server is up and whether it in turn is also properly configured.”
After looking into the issue more we noticed the Exchange certificate enabled for UM was incorrect and had the wrong subject name in the certificate. To sort this we re-created a new certificate with the correct Subject name and enabled for UM. We then restarted the Exchange UM service and all started working