Блокировка происходит на серверах Microsoft.
В целом крупные вендоры вроде Microsoft/Google/AWS борются с любыми новыми IP адресами для отправки почты, есть такой термин "прогреть IP"/"warm IP", это не особо простая задача.
Выхода тут два (корректно настроенные SPF/DKIM/DMARC/PTR и другие пасы, к сожалению не помогут):
1. Продолжить пользоваться и получать жалобы о недоставки почты, ждать что компании признают ваш почтовик легитимным (продолжая переписку с поддержкой МС, однажды я добился что они разрешили два адреса публичных, но там была веская и уважительная причина, адреса принадлежали крупному вендору в западной Европе)
2. Приобрести сервис с прогретым адресом и рилеить через него.