550 Verification failed: No such user. Sending mail with Mailgun to CPanel email

I am creating a webservice with Mailgun to send out emails. It will BCC my own domain’s email for every email sent out. Assuming my domain is “example.com”. For every email sent out to a customer, say, [email protected], I will BCC its content to [email protected].

Currently, the domain example.com and its email is hosted on a server with CPanel.

In Mailgun, I have added and verified the domain example.com. Using this domain, I’ve sent a mail to [email protected] and [email protected]. The email is sent without issues to Gmail, however when sending to [email protected], I keep getting the error Server response: 550 550 Verification failed for <[email protected]> No Such User Here.

What’s baffling here is that if i send the email via Mailgun with another verified domain such as anotherexample.com, and then using this, I send my mail to [email protected]. The email arrives perfectly fine without errors.

So far, the things I’ve tried:

• Added Mailgun suggested SPF and DKIM
• Modified SPF to include my CPanel server’s IP (together with Mailgun SPF)
• Deleted both the SPF and DKIM (one at a time and both at once)
• Verified that the email [email protected] exists. Using the CPanel webmail’s interface, I can send and receive emails just fine.
• Tried updating the CPanel MX entries Email routing from Local -> Automatic -> Remote. (“Local” works the best. If its set to “Remote”, email sending and receiving doesnt work at all, even if mails are sent through Gmail/Hotmail).

My current MX settings are:

Priority 0: mail.example.com

My current Zone file records on CPanel:

example.com        A          <some ip>
mail.example.com   A          <same ip as above>

The code I am using to send mails via Mailgun (Ruby):

mg_client = Mailgun::Client.new 'xxxxxxxxxxx'
message_params = {:from    => from_email,
                  :to      => customer.email,
                  :bcc     => bcc_email,
                  :subject => MessageTemplate.email_subject,
                  :text    => message}
result = mg_client.send_message('example.com', message_params).to_h!

I currently do not have the SPF and DKIM records in the zone files. I’ve added and removed them and they had no effect on the error (still delivers fine to Gmail too).

I’ve spend the whole on this, scouring forums and whatnot but can’t seem to find a solution.

If at all relevant, I have a 301 redirect of example.com to www.example.com(Which has a CNAME pointing to another server). But I’ve researched and found out that 301 redirect does not affect emails.