Mailgun: '550 Requested action not taken error' when sending to certain domains

Question

I am using mailgun to send mail and am receiving this error message:

550 Requested action not taken: mailbox unavailable invalid DNS MX or A/AAAA resource record

when I send mail to certain domains. An example of a problematic domain is web.de

Sending to other domains via mailgun works just fine and in fact I am able to send mail to the problematic domain just fine from my own account (gmail).

In terms of DNS records, Mailgun indicates that my domain has been verified using TXT DNS records.My MX records point to another email provider that I am using to receive e-mail.

Answer 1

In case anyone was following this, it turns out the solution is to add MX records in your DNS to identify the Mailgun server. These are the records you'll want to associate with the subdomain mg.yourdomain.com:

mxa.mailgun.org  10
mxb.mailgun.org  10

The idea is that certain email servers do an MX lookup on the domain of the sender of the email (in this case mg.yourdomain.com). If those MX records do not exist, the server will reject the mail.

Note: in my case I already had separate MX records associated with my base domain (yourdomain.com) which were pointed to a different email client (not mailgun) that I was using to receive mail. So I was initially confused as to how/why I needed to add others, and whether it was valid. It turns out it is indeed valid (and this case, necessary) to have separate MX records for separate subdomains.