Are you using an Authenticated user account or are you just trying to send the email without authentication.
If you are trying to send an email using a user account, the maybe you should make sure that the username and password haven't changed.

Based on the server address, it appears that you are sending email messages directly without a user account. Sometimes Office 365 can be a pain trying to send email messages without a user account. Here is a way to do it. You will need their IT help.
https://docs.microsoft.com/en-us/ex...application-to-send-email-using-office-3

You mentioned that the voicemail gets deleted.Normally this will only happen once the email is accepted by the email server. If the email message fails to send, then the voicemail should still be in the user's voicemail box. I think that the email messages are being accepted by the Outlook 365 server but then filtered as junk automatically. Have their IT look at the link above.