Email server can send internal, but messages never arrive at external recipients

I'm running MailEnable on my server, and have been for many years. Recently we had an attack on our server, and I was able to close the hole.

Since then, our mail server doesn't seem to be sending mail out.

• If I send an email from myself to another account hosted on the server, the email arrives as expected.
• If I send an email from my gmail account to my business account, the email also arrives as expected
• The problem comes when I send from my business account to an external domain
  • I tried the following
    • Gmail.com
    • Hotmail.com
    • Shaw.ca
  • When I send to any of the above
    • The message leaves my client as expected,
    • The logs appear to accept and forward on the message
    • The SMTP outbound que is empty
    • The message never arrives
  • I have checked our domain with
    • mxtoolbox.com
    • senderbase.org
      • And neither of them are reporting any problems with our domain.
  • I have ensured that port 25 is open (along with the other standard ports)

Here is one of the log entries from the SMTP connector

11/05/13 12:10:00   SMTP-IN 494C0AF55CD0400FB90FD5E6525BC885.MAI    1312    127.0.0.1           220 mx1.example.com ESMTP MailEnable Service, Version: 6.81--6.81 ready at 11/05/13 12:10:00    0   0       
11/05/13 12:10:00   SMTP-IN 494C0AF55CD0400FB90FD5E6525BC885.MAI    1312    127.0.0.1   EHLO    EHLO ASSP.nospam    250-mx1.example.com [127.0.0.1], this server offers 6 extensions    159 18      
11/05/13 12:10:00   SMTP-IN 494C0AF55CD0400FB90FD5E6525BC885.MAI    1312    127.0.0.1   EHLO    EHLO ASSP.nospam    250-mx1.example.com [127.0.0.1], this server offers 6 extensions    159 18      
11/05/13 12:10:01   SMTP-IN 494C0AF55CD0400FB90FD5E6525BC885.MAI    1312    127.0.0.1   AUTH    AUTH LOGIN  334 VXNlcm5hbWU6    18  12      
11/05/13 12:10:01   SMTP-IN 494C0AF55CD0400FB90FD5E6525BC885.MAI    1312    127.0.0.1   AUTH    {blank} 334 UGFzc3dvcmQ6    18  26  [email protected]
11/05/13 12:10:01   SMTP-IN 494C0AF55CD0400FB90FD5E6525BC885.MAI    1312    127.0.0.1   AUTH    Y29sb25lbGZhY2U=    235 Authenticated   19  18  [email protected]   
11/05/13 12:10:01   SMTP-IN 494C0AF55CD0400FB90FD5E6525BC885.MAI    1312    127.0.0.1   MAIL    MAIL FROM:<[email protected]>   250 Requested mail action okay, completed   43  31  [email protected]   
11/05/13 12:10:01   SMTP-IN 494C0AF55CD0400FB90FD5E6525BC885.MAI    1312    127.0.0.1   RCPT    RCPT TO:<[email protected]>   250 Requested mail action okay, completed   43  35  [email protected]   
11/05/13 12:10:01   SMTP-IN 494C0AF55CD0400FB90FD5E6525BC885.MAI    1312    127.0.0.1   DATA    DATA    354 Start mail input; end with <CRLF>.<CRLF>    46  6   [email protected]   

Here are the headers of the sent message

X-Assp-Version: 1.7.5.7(1.0.07) on ASSP.nospam
X-Assp-ID: ASSP.nospam 78601-04523
X-Assp-Intended-For: [email protected]
X-Assp-Envelope-From: [email protected]
Received: from [10.10.1.101] ([68.147.245.149] helo=[10.10.1.101]) with
    IPv4:587 by ASSP.nospam; 5 Nov 2013 12:10:00 -0700
From: Chase Florell <[email protected]>
Content-Type: text/plain
Content-Transfer-Encoding: 7bit
Subject: Test Message
Message-Id: <[email protected]>
Date: Tue, 5 Nov 2013 12:10:18 -0700
To: Chase Florell <[email protected]>
Mime-Version: 1.0 (Mac OS X Mail 7.0 \(1816\))
X-Mailer: Apple Mail (2.1816)

.

Where else can I check to see if there is something broken? What could cause a problem like this whereby the message appears to send, but never arrives, and never returns a bounce?