Relay Access Denied 5.7.64 Tenant Attribution

We’ve run into a problem were we are unable to set up an email relay within our network that will relay to Office 365 and then out from there. We’ve been through article after article found through Google but none have resolved.

The problem is that when relaying to an address outside our domain, we receive an error message stating:

"Mailbox unavailable. The server response was: 5.7.64 TenantAttribution; Relay Access Denied [CO1NAM04FT026.eop-NAM04.prod.protection.outlook.com]"

The original host name we connect to is  [domain].mail.protection.outlook.com where [domain] is the specific host assigned to us.

This error is occurring when attempting to relay mail through the server from C#.

Code looks as follows:

var hostName = ConfigurationSettings.AppSettings[mailServerKey];

using (SmtpClient client = new SmtpClient(hostName))

{

    //  Have also tried without credentials

    client.Credentials = new System.Net.NetworkCredential("MailAddress", "Password");

    client.Port = 25;   // Have also used 587

    client.EnableSsl = false;   // Have used true with port 587

    for (int i = 0; i < mailArray.Count; i++)

    {

        try

        {

            //Retrieve the MailMessage object

            MailMessage mail = (MailMessage)mailArray[i];

            client.Send(mail);

        }

        catch (System.Exception e)

        {

            LogError(e);

        }

    }

}

Any suggestions for a next step to take would be appreciated.

Thanks,

Jim