From CME, try the below steps:
voice service voip
allow-connection sip to sip
no ip address trusted authenticate
dial-peer voice 100 voip
destination-pattern 5555 << Your voicemail pilot
session protocol sipv2
session target ipv4:1.1.1.1 (1.1.1.1 is your office 365 - if you need to specify a different port you can use: session target ipv4:1.1.1.1:5063)
telephony-service
voicemail 5555 << defines voicemail pilot
Try above and see how it goes.
-Terry
Please rate all helpful posts