Voice Mail from traditional phone system providers such as Cisco and Avaya is expensive and I migrate 5-10 large customers each year to Office 365 for Voice Mail. You see for the cost of and SBC they got a good voice mail service for free from Microsoft.
Not anymore. Now they only way to use a legacy PBX with Office 365 is migrate to Skype for Business for telephony (ditch existing telephony), Migrate back to premise for Email and Voice Mail (because they must be hosted together) or buy a third party voice mail platform (spend more money).
In a time when Microsoft is growing cloud this that makes you wonder what they heck they are thinking or can you trust them when the begin taking cloud features away?