Exchange2013 UM integration with Lync2013 fails

In my lab setup I have Exchange 2013 CU1 server with Mailbox and CAS role installed. Exchange UM is enabled and integrated with Lync Server 2013 CU1. As Exchange 2013 does not have an Edge Transport role, the lab environment uses Exchange 2010 as the Edge Transport server. Below is the simplified diagram of the setup (firewalls and reverse proxy omitted).

Everything was working fine until Lync Phone Edition (LPE) devices and VVX Lync-compatible phones were no longer able to access the Exchange Voicemail subscriber access and auto-attendant like they used to. A quick test using the Lync client also had issues accessing the Voicemail and a snooper trace showed multiple following MS-Diagnostic errors:

"ms-diagnostics: 15007;reason="Exchange Unified Messaging server did not respond to request"
"ms-diagnostics: 1038;reason="Failed to connect to a peer"
"ms-diagnostics: 15030;reason="Failed to route to Exchange Server"

However, Exchange calendar integration continues to work on the LPE and VVX phones. This suggested that UM integration was failing because of an recent attempt to update the Exchange 2013 server to CU2. That update failed during prerequisite checks with an error message saying that there were one or more Exchange 2010 servers in the organization that has not yet been updated to SP3. However the Exchange 2010 Edge transport server was already running SP3 so it was unclear why this message appeared. To resolve this issue, I performed the following steps:

1. Remove the Edge Subscription on the Exchange 2013 server using the cmdlet 
    Remove-EdgeSubscription - identity <edgeservername>

2. Proceed to update to Exchange 2013 CU2. After the Exchange2010 server Edge Transport was removed the CU2 installation was able to complete successfully:

3. Next the Exchange Edge Transport server was updated to Exchange 2010 SP3 Update Rollup 2. This should complete without any errors. At this stage, the old Edge Subscription still exists and attempts to remove it will result in a incompatible Exchange version error as shown below:

To resolve this the object must be manually removed by running ADSIEdit on the Edge transport server and connecting to the "Configuration" naming context and computer "Servername:50389" as shown below. Then navigate to CN=Configuration, CN=Services, CN=Microsoft Exchange, CN=First Organization and delete objects which as a version of 88218628259840 as these are objects created by Exchange 2013. Typically these object will be in the Transport Settings->Accepted Domains container.

In my case, removing this single object with version 88218628259840 of was enough to successfully run the Remove-EdgeSubscription cmdlet on the Edge Transport:

4. To recreate the Edge Subscription, the cmdlet "New-EdgeSubscription -FileName "C:\EdgeSubscriptionInfo.xml" is run on the Edge Transport Server and the file copied to the Exchange 2013 Mailbox/CAS server.  Then run the following cmdlet on the Exchange 2013 server to create the subscription:
New-EdgeSubscription -FileData ([byte[]]$(Get-Content -Path "C:\EdgeSubscriptionInfo.xml" -Encoding Byte -ReadCount 0))
-CreateInternetSendConnector $true -CreateInboundSendConnector $true -Site  "Default-First-Site-Name"

To ensure edge sync is working we can use the Start-EdgeSynchronization cmdlet on the Exchange2013 server and obtain a success result:

5. Test Exchange UM on Lync client and Phones.. With the Edge Subscription issues resolved, Exchange UM integration was working once again on both the Lync clients and both the LPE and VVX phones. In summary, attempting to update Exchange 2013 CU2 caused Edge Subscription issues which in-turn affected Exchange 2013 UM and its integration with Lync 2013. Resolving those issues as shown in this article helped to get UM working again.