I still think this is DNS related.  

On the mail servers, run 'nslookup -querytype=mx example.com' where
example.com is the domain name of the other mail server's domain. 
IIRC, both are in private IP space behind the same firewall, so that
needs to resolve to the appropriate private IP.  My guess is you're
still resolving to the outside public IP.

If I missed something and one of these boxes is *nix, run 'dig mx
example.com' instead of nslookup.

-Chris