Relay Denied error comes due to 2 reasons.
1. Customer tries to send mail before authorization on the mail server.
2. Customer IP does not have hostname (Reverse look up failed).
Try this:
On most Email Clients, there is a setting on the "Servers" tab of the Account Properties, called "My Server Requires Authentication".
This setting is in reference to your SMTP (Outbound) Server. You just need to enable this setting by checking the box, and then click the "Settings" button nearby and insure that the "Use same settings as my incoming server" or "Log onto incoming mail server before sending mail" radio button is filled in. "Apply" these changes, close all windows, close out the Email Client completely, open it back up, try again.