To use the local Exchange server, SMTP had to be configured on the customer's UCx to send email that server. Now, after switching to Office 365, this configuration is no longer required.
Go to the System - Remote SMTP page and either turn it off or (if "off" does not work because they have the port 25 blocked) enter a proper configuration data of the Office 365 server.
To answer your initial question - yes, for me voicemail to email is working with Office 365 without any problems (SMTP turned OFF).