Telnet to remote domain problem

[SmokinRR]

I'm hoping someone may have some ideas. We were notified that our online system (which generates emails at the users request) was unable to deliver messages to one of their clients successfully, they were getting delay notifications. I checked that the mx record for this domain was being resolved to the correct IP address, and then tried to telnet from my server (that sends these emails) out to the receiving mail server with no luck. I then tried to connect to some other mail servers via telnet successfully, so I know that works. I am able to connect via telnet from all my other email servers (different domains) successfully, it is just this one server that cannot connect to the remote mail server.

Again, it is resolving the dns properly, however I cannot telnet to this server using the mx name or the IP address only from that one server. Anyone have any ideas??

Thanks in advance!

Jay