Question : Can't Solve Relay Access Denied Issues

I'm sorry to beat this issue any further, but i have had no luck on all my searches for a solution. I have a 2003 Server with Exchange 2003. I have various clients who are using RPC over HTTP and it has been very successful. In fact, 95% of the emails go through properly. At least every day however, one of my clients forwards me a message with an NDR. Sometimes it's the same, sometimes it is different. Here's what we might receive:

#5.5.0 smtp;553 sorry, mail to that recipient is not accepted (#5.7.1)>
smtp;554: Relay access denied
#5.7.1 smtp;550 5.7.1 Unable to relay for ...
;553 sorry, that domain isn't in my list of allowed rcpthosts (#5.7.1)>
5.5.0 smtp;550 No such user - psmtp
18591 is currently not permitted to

Now, i've tried many of the things that are suggested out there, with turning off/on SMTP Auth, i've verified that the reverse DNS is to my correct server address. I have a Barracuda firewall scanning incoming email, which i have removed and still get the messages. I've even gotten messages bounced back saying "no such user" when we are sure that there is a user at the destination address.

I get a 'relay access denied' when i, myself send a message to a particular domain. If i re-send the email two seconds later, the reciipient gets it.

I'm sorry to be so vague in my descriptions, but i' can't seem for the life of me to solve this problem once and for all! Any advice would be appreciated.

Answer : Can't Solve Relay Access Denied Issues

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.