Make sure you have your DMARC, SPF, DKIM all correctly setup. Then test some emails with this tool: https://www.mail-tester.com/

Go through the issues one by one and you should be all good.

I've used Mailgun for years with hardly any issues.