451 Validating Sender

[moegal]

I recently moved my mail server to another IP address after 10 years on the previous IP Address. After working out some blacklist and blocklist issues with the new IP address, everything seems to be working except for a few issues.

I checked all of my DNS records with mxtoolbox and everything looks fine. Most mail is coming thru just fine. Except:

A person is trying to send an e-mail to me and they are getting the following error. I checked on our server and this request does not even hit my server.

Anyone know what this is?

I think they are on an exchange server with mxlogic.net. A redacted message header is below.
===============================================
THIS IS A WARNING MESSAGE ONLY
YOU DO NOT NEED TO RESEND YOUR MESSAGE
===============================================

A temporary error occurred while delivering to the following address(es):

<xxx@xxxx.xxx>: 451 Validating Sender:

I will continue trying to send the message until it is delivered or expires.

*********************************************************************************************
message header:

Received: from unknown [nn.nn.nnn.nn] (EHLO xxxxx.xxxxx.local)
by xxxxx.mxlogic.net(mxl_mta-7.2.2-0)
with ESMTP id xxxxx.mxlogic.net (envelope-from <xxxxx@xxxxx.com>);
Mon, 27 Jan 2014 13:42:11 -0700 (MST)
X-MXL-Hash: xxxxx-xxxxx
Content-class: urn:content-classes:message
Subject: RE: xxxxx
MIME-Version: 1.0
Content-Type: multipart/related;
boundary="----_=_NextPart_001_01CF1BA1.69181CCA";
type="multipart/alternative"
Date: Mon, 27 Jan 2014 15:50:27 -0500
Message-ID: <xxxxx@xxxxx.xxxxx.local>
X-MimeOLE: Produced By Microsoft Exchange V6.5
In-Reply-To: <!&!AAAAAAAAAAAYAAAAAAAAABlE/uvPnXhKrUu5ZiMs/uXCgAAAEAAAANPHFoYjlEdBrgHTqlZ9unkBAAAAAA==@xxxxx.com>
X-MS-Has-Attach: yes
X-MS-TNEF-Correlator:
Thread-Topic: xxxxx
thread-index: AQLoMs797Oz2KMhf1HzMZv8tqqnJ+Jhm0A6AgAAGVSCAAAaEoA==
References: <xxxxx.xxxxx@xxxxx.com> <xxxxxx@xxxxx.net> <!&!AAAAAAAAAAAYAAAAAAAAABlE/uvPnXhKrUu5ZiMs/uXCgAAAEAAAANPHFoYjlEdBrgHTqlZ9unkBAAAAAA==@xxxxx.com>
From: "xxxx xxxxx" <xxx@xxxxx.com>
To: "xxxxx" <xxxxx@xxxxx.com>
Cc: <xxxxx@xxxxx.net>

Any help would be appreciated.
Marty

[Admin]

Hi,

It looks to be a configuration issue their end. The temporary error ("validating sender") is not coming from MailEnable. Only info I could find was the temporary error was being returned by mxlogic when they are filtering their outbound email:

https://support.mcafeesaas.com/MCAFEE/_ ... &aid=27819

Did the sender use to email you ok before your IP change? Do they get the error sending to anyone else?