Ooops

That's the error I got when I tried to send a test mail to a mailbox.

We observed that external emails were not coming in so we decided to test.

Message not delivered
Your message couldn't be delivered to [redacted] because the remote server is misconfigured. See technical details below for more information.
The response from the remote server was:
550 5.7.1 Relaying denied

The first thing that came to my mind was the DNS records, I went through them and confirmed that the MXs were good. I recently switched to the present DNS provider. So that is a suspect.

I researched the 550 5.7.1 Relaying denied and found out that it's truly related to DNS misconfiguration.

Went through the DNS records again, giving attention to the MXs, and realized that there is Mailgun mx record, we stopped/deactivated our Mailgun accounts a while ago. The suspect is pinned down.

I then proceeded to delete MX records that pointed to Mailgun, waited for some minutes then retried sending a mail test.

No more errors, mail well received.