What are the error messages? What do the logs look like on $relay's mail transfer software? Is your incoming IP address permitted to send to anywhere by $relay? (Note: this would not be the default, as it means the system is an open-mail-relay, forbidden by network standards.)