Can't Solve Relay Access Denied Issues

Relay access denied, means a server will not send the message because it is configured not to do so. Either because the sender is unknown or the IP from where the email is coming is unknown.

First, looking at the latter, a server might employ SMTP authentication (with, or without SSL or TLS) or POP BEFORE SMTP authentication to tell the server that the connecting IP address (client machine) is allowed to send email and the server will relay in this case. (I hope your machine is not an open relay so you should be employing one of these 2 methods).

Second, not all NDR are legitimate, some are spam, however I'm guessing we can rule that out as a possibility for now and we are dealing with a real issue.

Setting up a PTR record with whoever manages your IP address/range is a good idea to minimize spam, since receiving mailservers or anti-spam appliances (like Barracudas) might do a reverse DNS check to see if it matches the hostname in the email header.. if not, it may be tagged as spam.. However...though it may be tagged, it is unlikely to generate the above mentioned error messages. It will more likely generate a 451 or 452 message (if any at all).

In a case like this, it would be very useful if you have access to the mailserver logs, particularly from the smtpd daemon/service or better yet, if you can record the SMTP conversation between the servers. Either with a "recordio" like utility or a TCP sniffer in verbose mode to troubleshoot the issue.

If that is not an option, open a telnet window on port 25 to your mailserver and manually inject a message. Sometimes you get a more meaningful error message there: Just search Google for "telnet test smtp" and many hits will come up.

Lastly, the above error, really is a relaying issue, sometimes this happens because of DomainKeys or SPF violations. Is your mailserver using this? To what behaivour is it set? tag only or does it do more? If there is an anti-spam appliance in between (like the Barracuda), what do these logs say? Probably they would say "allowed", but they can still be blocked for technical reasons or SPF violations.  For example if Domain A sends to you through the Barracuda then it will be blocked since the Barracuda is not in the SPF record of Domain A. and will not arrive at B, though this should generate another message (and not one of the above).

Is the server GC?

Apologies on all the late replies...The problem was that my domain manager had an SSL arranged and pointing to the domain 'mail.theserver.com', whereas my server's actual name (net BIOS and all) was exchange.theserver.com. The ssl was mismatched and I am positive that this mismatch affected the reverse look up. Most recipients did not care if their servers didn't do reverse lookups, but for the odd percent that did, it was a huge pain.

While i could have probably re-generated an SSL, and reconfigured the domain settings to match that of my server, i was in no way going to change the 'server' name of a running exchange box. I created a new domain, new SSL and ensured that it all matched, then migrated all of my users to a new server. Yes, definately 'overkill', but it worked and never got a 571 again.

Phew.

Thanks to all those that contributed.

So you're GC?