Question : Exchange email issue: #5.5.0 smtp;550 <*****@goran-ando.com>... Relaying denied

When anyone from my domain tryings to send to the goran-ando.com domain, intermittently (maybe 1 in 5), we will get a return back saying "There was a SMTP communication problem with the recipient's email server.  Please contact your system administrator. ... Relaying denied>".

A little about my exchange environment:
- 1 exchange sever
- No connectors
- PTR, MX, DNS, everything is setup corrently and verified using DNSstuff
- Running TrendMicro Message Scan which has already been ruled out as a issue

I also checked with the host of goran-ando.com and they claim nothing is wrong on their side. However, MessageLabs (goran-ando.com) has more than one server. Is it possible that just one of their servers has a problem with our domain?

Any ideas how to fix this if it is on our side, if it is infact on our side? It's a big problem because he actually works for my company but is still keeping his outside email address. Thanks.

Answer : Exchange email issue: #5.5.0 smtp;550 <*****@goran-ando.com>... Relaying denied

I have seen this with other hosted services. In the end I turned on SMTP logging so i could see which server was involved in the conversation.

I then telnetted onto this server to send a test email and it failed... tried one of the servers that according to the logs worked and it was fine.

When I went to the hosting company they were able to find an issue that was then resolved.

http://www.msexchange.org/tutorials/Logging_the_SMTP_Service.html

http://www.yuki-onna.co.uk/email/smtp.html