Windows server and Kyocera photocopier can no longer send emails through Office 365 SMTP server (domain.mail.protection.outlook.com). The issue started happening after ISP change (new ISP was UK's PlusNet). After checking PowerShell mail send script output I found following error:
Exception calling "Send" with "1" argument(s): "Mailbox unavailable. The server response was: 5.7.1 Service unavailable, Client host [80.229.xxx.xxx] blocked using Spamhaus.
To resolve the issue I had to request for the IP to be removed from spamhaus PBL block list. The PBL block list is not SPAM sender list, it mostly has residential IP address ranges that normally shouldn't be sending unauthenticated SMTP emails directly. You can find more information about this here.
After completing the removal request it took about 30 minutes for emails to be accepted by Office 365 SMTP servers.