Question : Exchange delivery problems in only one direction

We have two clients hosted on a common ISP.  These clients are completely different in terms of domain memberships, but they do have the need to email between the two organizations.  Client A is running Exchange 2003, and Client B Exchange 2007.  Client B can get email through to A without issue, but attempts from A to reply to emails sent by B fail with NDR #5.1.1.  Because the failing messages are direct replies, we know the end-user email address is correct.  The problem seems to be somewhere in Client A's network/Exchange, as it appears that the NDR is coming from is coming from A's Exchange server for some reason (when it should really come from B's server if the email is routed properly, correct?).  What could be causing this?  We've checked and flushed DNS cache on A's side to no avail.  

Answer : Exchange delivery problems in only one direction

That's the strange part.  Client B has no problems receiving email from any other domain/IP.  Also, Client A has no problem sending to any domain besides Client B.  Could it have anything to do with the common ISP?  The two WAN IPs are only one hop apart.