I was having some issues with mailgun not delivering my messages. Apart from the MX DNS records, all the DNS settings were correct according to mailgun. However, I got the following error:
Server response: 550 550 Sender has no A, AAAA, or MX DNS records
It is kind of a cryptic message by Mailgun, especially because the DNS check is telling that the settings are correct.
However, the response from the processing mail server is basically saying that there is no A record known for the sender.
During the DNS setup for mailgun, a sending domain 'mg.your-domain-name.tld' was created for mailgun to use. In practice (not all, but at least some) mail server do a check to see if the domain name 'mg.your-domain-name.tld' matches the sending IP address. Therefor you need to add an A record in your DNS settings for mg.your-domain-name.tld and let it resolve to the IP address of the server handling the mail (often the same server IP as the www-record).
After the record has been processed and propagated, you can verify that the subdomain is resolving by issuing a ping command:
$ ping mg.your-domain-name.tld
This should return answers from the IP address you've configured in your DNS settings.