If it is giving you relay access denied when you are trying to send an email from outside your network to a domain that your server is not authoritative for then it means your receive connector does not grant you the permissions for sending/relaying. Most likely what you need to do is to authenticate to the server to be granted the permissions for relaying but that does depend upon the configuration of your receive connector. In Exchange 2007/2010/2013 you would need to enable ExchangeUsers permission group as well as an authentication mechanism such as Basic authentication.
Once you're sure your receive connector is configured make sure your email client is configured for authentication as well for the SMTP server. It depends upon your server setup but normally for Exchange you would configure the username by itself, no need for the domain to appended or prefixed to it.
To test things out with authentication via telnet you can go over my post here for directions: https://jefferyland.wordpress.com/2013/05/28/essential-exchange-troubleshooting-send-email-via-telnet/