Basically, when you need to have Lync Hybrid setup with Skype for Business Online ("SfBO" - same below), or when you are doing Exchange Hybrid with Exchange Online in an environment where there is already Lync setup with Unified Messaging, you have to make sure that there are no CSStaticRoute that exists, or else co-existence will fail.
- Lync Hybrid only: On premise Lync users cannot initiate IM with migrated SfBO user
- Exchange Hybrid with Unified Messaging: When calling the user's extension number, the call is directed somewhere else and not to the user's voicemail
This all boils down to the fact that when SharedAddressSpace is configured in Lync on premise with SfBO, CSStaticRoutes are no longer supported, and have to be deleted.
To confirm that you have a static route, run the following from Lync Management Shell:
Get-CsStaticRoutingConfiguration -identity global | Select-Object -ExpandProperty Route
The quickest way to fix this is to issue the following command to delete all static routes:
Set-csstaticroutingconfiguration -identity global -route $null
Wait for a few minutes and the problem will resolve itself.
OK, you might ask what are the effects of deleting all CSStaticRoutes - it could range from breaking your Polycom RMX integration with Lync to breaking a PSTN conferencing solution.
Unfortunately I have no advice on how to get around with this, other than paying a support ticket to Microsoft and get them to work with the third party vendors.
I was lucky because the customer no longer wants to use the RMX integration, and Polycom RMX integration does not work with Skype for Business Online anyway.
Hope this helps someone.