‎All outgoing mail from Microsoft 365 tenant to outlook and yahoo mark as spam at receiver end

Hello all, I’m encountering an issue with sending emails to external providers. Despite a successful migration from our hosting provider’s mail server to the M365 server two nights ago, and ensuring that the MX records, TXT record, and CNAME record are correctly filled in the hosting provider zone editor, my emails are still landing in the recipients’ junk folders.

I’ve also added DMARC and DKIM entries, but this hasn’t resolved the issue. Initially, we had problems with Gmail as well, but after adding DKIM and DMARC records to the hosting provider zone editor, this was fixed. However, emails sent to outlook.com and yahoo.com continue to end up in the junk folder.

Interestingly, all incoming emails are being delivered to the inbox without any issues. Moreover, if an email is sent from outlook.com to my Microsoft 365 tenant email address, and I reply to that email, my response goes directly to the inbox instead of the junk folder. This means that an outlook.com user needs to send me an email first for my outgoing mail to avoid the junk folder.

I would greatly appreciate any suggestions or solutions to this problem. Thank you.