Hi,
To narrow down the issue, we can try to send mail to a Gmail/Outlook account, see if the mails also are pushed in to spam folder. If you can send mail to those mail accounts without issue, there might be a chance that some rules set in client side blocked your domain or address.
DMARC records might lead to this. Quote However, if you do publish a DMARC reject policy but dont have all of your email authenticated, some of it may be marked as spam for inbound email (as described above), or it will be rejected if you do not publish SPF and try to relay it outbound through the service. For detailed information on DMARC, you can refer to This Article.
And this forum is the best place for Office 365 domain management related questions.
Thank you.