Got asked to solve an issue where Voicemail for users in a Lync onprem, UM in cloud environment had mysteriously stopped working.

The FE event log had this to say
Running Lync Traces showed the following
Followed by the Error
So as exchange UM is in the O365 cloud and the event says to check that off I went.
Steps to check O365 UM configuration with Lync on premises
I’ll start with checking the Lync setup
1. What DNS is required? port 5061 dest Edge FQDN 
         Edge FQDN
2. Ensure Access Edge Configuration is correct
3. Check the Hosting Provider
4. Check the UM Contact Object
5. Make sure that a test user is enabled for Hosted VM
6. Check the Hosted Voicemail Policy 
7. Make sure that the Edge Server is replicating
Now let Check the O365 configuration
1. Check that the UM Dial Plan is setup. Now this is really simple, there is absolutely no trick at all. Just remember that there wont be an IP gateway. Thats it!
2. Check to see the Authoritative domain in O365 matches the Organization configured in CsHostedVoicemailPolicy by running Powershell remotely to connect to O365 deployment.
From Powershell…
$cred = Get-Credential
$s = New-PSSession -ConfigurationName Microsoft.Exchange -ConnectionUri -Credential $cred -Authentication Basic -AllowRedirection
importresults = Import-PSSession $s
Note the Results.
In my case this is where the problem was, somehow … mysteriously the Authoritative Domain had changed.

Now I have see this else where, when I have the opportunity to investigate why I’ll come back and post an update.