Why a server has to refuse this
A server that forwards mail from arbitrary senders to arbitrary recipients is an open relay. Such systems are abused for spam within hours and end up on every blacklist afterwards. Refusing is therefore the correct default, and “Relay access denied” is rarely a defect on the far side.
The three causes
- Sending without authentication over port 25. The most common case with home-grown scripts and devices. Your own mail belongs on the submission path: port 587 with STARTTLS and SMTP AUTH, or 465 with implicit TLS. Port 25 is for server-to-server traffic only.
- Delivering to the wrong server. The mail goes to a host that is not responsible for the recipient domain at all — because MX records still point at the old address after a migration, or a smarthost is hard-coded that no longer serves the domain.
- The recipient no longer exists on that server. After a domain move the old server does not know the address any more and rejects it as foreign — technically the same message, substantively a recipient problem.
Narrowing it down
First establish which server is actually responsible for the recipient domain. If the host your system delivers to differs from that, you have found the cause.
dig +short MX recipientdomain.com
For your own outbound, check:
port 587 instead of 25? SMTP AUTH enabled? credentials configured?
If instead the message appears on inbound mail to your own server, the recipient domain is missing from its list of responsibilities — in Postfix that is mydestination, virtual_mailbox_domains or relay_domains.