I had deliverability issues with Mailgun that I fixed by adding MX records for our Mailgun subdomain:
https://documentation.mailgun.com/quickstart-receiving.html#add-receiving-mx-records
It’s a bit counterintuitive, because we’re not receiving emails through Mailgun. But here’s what Mailgun’s support told me:
The error (which is called Sender Address Verification) that you are seeing is due to the recipient server performing a MX lookup on the envelope.mail-from address and failing to find the records for the domain listed. Some email servers check the domain in this envelope.mail-from field for MX records, and if the records do not exist, the email servers reject the message. Therefore, by adding Mailgun’s MX records to your domain, the MX lookups of those email servers should succeed, and the servers will accept your messages.
Hope this helps other frustrated folks!