Relay Access Denied----#5.7.1 smtp

We are not able to send message to one client domain and we are getting an error message that says "The following recipient(s) could not be reached:
user@clientdomain.com.au on 15/10/2007 11:33 AM
You do not have permission to send to this recipient. For assistance, contact your system administrator. <domain.com.au #5.7.1 smtp;554 5.7.1 <user@clientdomain.com.au>: Relay access denied>"

But we are able to receive the email from them. If I am trying to telnet their mail server, then 110 is successful but 25 failed. Can anyone tell me which mail server issue is this, is it my client server or only the server? Thanks.

You can try to solve this issue by changing the FQDN in your SMTP Virtual Server to match the server's external name. When the server is currently advertising itself as .local then you will get the same error message that you have listed. Go to ESM, Servers, <your server>, Protocols, SMTP and then right click on the SMTP VS and select Properties. After that click on the tab delivery and then advanced. After that change the FQDN from server.domain.local to mail.domain.com and then apply and ok.