Email replies receive: Reason: Illegal host/domain name found

[AAO289]

I have had this happen several times to one domain.  If I reply to an email message (from folks I regularly communicate with), I periodically receive a message: " Reason: Illegal host/domain name found  "

If I reply again minutes later to resend the message it goes through fine.  But it is happening enough to be a frustration.  It has happened four times recently with three people at this domain.

Here is the header with email addresses & Subject edited.

This report relates to a message you sent with the following header fields:

Message-id: <20141209214030.6160533.84847.7847@verizon.net>

Date: Tue, 09 Dec 2014 16:40:30 -0500

From: My Name <myemail@verizon.net>

To: Receiver Name <Receiver.Name@nassauchurch.org>

Subject: Re: EMAIL SUBJECT LINE

Your message cannot be delivered to the following recipients:

Recipient address: Receiver.Name@nassauchurch.org

Reason: Illegal host/domain name found

[tns2]

Typically this is something at the Email Receivers location.

[broppoli]

---

@tns_2 wrote:

Typically this is something at the Email Receivers location.

---

In this case, it is not. I am an administrator of a Exchange Server who is seeing this same problem. People who email ourdomain.org with Verizon.net accounts are receiving 5.4.4 (Ilegal host/domain name found). Only one person has reported it, but this is not the first time this has occured recently with verizon.net accounts. Another engineer in my company has seen the exact same scenario on a different Exchange Server awaiting messages from verizon.net.

1. SPF and MX records for ourdomain.org are properly resolving on many DNS servers around the world. 

Verizon needs to look into this.

[tns2]

The other reasons I know of are missing MX records and banned Email domains.

I would guess Verizon uses its own DNS servers and they may have lost the MX record.

NOTE IF THAT IS THE CASE, this is a peer to peer forum and not a place to contact Verizon for the problem.