MX Change

One of my clients are wanting to use a 3rd party spam screening service, which is supposed to only require a change of their MX entry, but it's not working for me.

When I change the MX, and send a message to the account, I get the following message kicked back at me.

Quote:

This message was created automatically by mail delivery software.

A message that you sent could not be delivered to one or more of its recipients. This is a permanent error. The following address(es) failed:

receiver@theirdomain.com
SMTP error from remote mail server after RCPT TO:<receiver@theirdomain.com>:
host mail.mailroute.net [199.89.0.201]: 554 5.7.1 <receiver@theirdomain.com>:
Relay access denied

------ This is a copy of the message, including all the headers. ------

Return-path: <me@mydomain.com>
Received: from d142-179-125-92.bchsia.telus.net ([142.179.125.92]:62140 helo=WorkLaptop)
by server.mydomain.com with esmtp (Exim 4.63)
(envelope-from <me@mydomain.com>)
id 1HAZU5-0000Rk-8c
for receiver@theirdomain.com; Fri, 26 Jan 2007 16:23:49 -0600
From: "Work" <me@mydomain.com>
To: <receiver@theirdomain.com>
Subject: Test
Date: Fri, 26 Jan 2007 14:23:49 -0800
MIME-Version: 1.0
Content-Type: multipart/alternative;
boundary="----=_NextPart_000_0045_01C74155.999394C0"
X-Mailer: Microsoft Office Outlook, Build 11.0.5510
X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.3028
Thread-Index: AcdBmJ0b1GRT8lMDSveqOjg5CgqmkA==

This is a multi-part message in MIME format.

I know this has something to do with my mail server only trying to send the message once, and not again. I'm setup with RHEL w/cPanel.