Vanilla Asterisk version 13.20.0 and 15.3.0 with same results. IMAP storage and retrieval works. MWI enable works. MWI works both ways if voicemails are not stored locally. Phones are registered to a Cisco CM so I use externnotify. I ran a trace and found no packets going to O365 after the voicemail was left.
Important bits of voicemail.conf:
externnotify = /root/mwi.sh
imapserver = outlook.office365.com
imapport = 993
imapflags = ssl
pollmailboxes = yes
pollfreq = 30