Exchange 2003 SP2 421 error

We have an Exchange 2003 SP2 server that was recently used as an open relay and tagged on 5 blacklist sites.  We closed open relay and went through the removal process and everything comes up clean on all test now.  Although now we are having intermittent problems receiving some mail and maybe sending (no NDRs coming back but people dont respond, could be in there junk mail though).  The main concern is sometimes people sending to our server get NDRs and sometimes they dont.  Below is one of those NDRs.  I have checked all filters on the Exchange server and matched them to another Exchange server in another completley different site which works great.  Also i have checked all DNS issues and everything can resolve properly when pinging the sites that cannot send to us.  Also, there is NOTHING logged in eventvwr in any log about any issues at all with Exchange.  Any ideas?  (anything with ***priveateremoved, or email was here was removed for privacy)

From: Mail Delivery Subsystem
[mailto:MAILER-DAEMON@****domain name went here*****]
Sent: Friday, February 23, 2007 1:26 PM
To: *******email address was here*****
Subject: Warning: could not send message for past 4 hours

    **********************************************
    **      THIS IS A WARNING MESSAGE ONLY      **
    **  YOU DO NOT NEED TO RESEND YOUR MESSAGE  **
    **********************************************

The original message was received at Fri, 23 Feb 2007 08:04:00 -0600 from [165.221.20.100]

   ----- Transcript of session follows ----- ... while talking to
mail.*****privateremoved.org.:
>>> DATA
<<< 421 Transmission channel timeout.
<****Private email address was removed*****>... Deferred: 421 Transmission channel timeout.
Warning: message still undelivered after 4 hours Will keep trying until message is 5 days old