Mailsonmota,
Existem alguns detalhes que devem ser observados:
1 - Como o colega Fernando_dos_Santos colocou, verifique a configuração do seu DNS reverso, ele é primordial para a configuração de e-mail
2 - E-mails enviados de novos IP's dentro de uma organização tendem a ser classificados como SPAM depois da mudança de IP.
3 - Verifique sua reputação de IP junto as ferramentas de monitoração, tanto da google como da Microsoft:
https://sendersupport.olc.protection.outlook.com/snds/JMRP.aspx?wa=wsignin1.0
JMRP e SNDS Microsoft: você tem acesso a reputação do IP e relatórios de e-mails classificados como SPAM do seu domínio entre outras facilidades.
https://www.blog.clubehost.com.br/inscrevendo-se-no-microsoft-jmrp-e-snds
A ferramenta da Google é o Postmaster Tools:
https://support.google.com/mail/answer/6227174?hl=en
Com essas duas ferramentas das duas maiores provedoras de serviço de e-mail da internet hoje, você consegue sempre identificar alguma falha pontual.
Outra ferramenta é o mxtoolbox, ele faz uma verificação quanto a registros DNS, SPF e todo o resto:
https://mxtoolbox.com/MXLookup.aspx
Verifique essas configurações e veja se está tudo ok
IT Specialyst | Azure Administrator | MCSE Core Infrastrucuture | MCSE Produtivity | VCP6-DCV | Commvault Professional | MBA | Se a resposta for útil, marque! | If the answer is helpfull, check!