Is a firewall blocking your Exchange Server's SMTP/POP3 communications!!!

It is interesting to note that if you have a cisco PIX firewall sitting in default security configuration somewhere between your exchange servers it is bound to cause hell lot of problems.

Exchange relies on three propreitary ESMTP verbs (X-EXPS, X-LINK2STATE and XEXCH50) for proper functioning and many others as well.
The stupid Mailgaurd feature, that is on by default, on Cisco PIX firewall allows ONLY RFC 821 SMTP commands to flow across (HELO, MAIL, RCPT, DATA, RSET, NOOP and Quit). All other commands are translated into X's.

When this happens, a number of symptoms can manifest:

• Link state table does not update correctly
• Mails keep pending to be submitted to sibling mail servers in a same Rotuing group
• Exchange servers can't authenticate each other.
• Seemingly commonplace commands are responded to with the 500 Unrecognized command error or one of its analogues.
• Normal commands produce completely unexpected responses

You would need get the Mailgaurd feature disabled in the PIX firewall that is sitting between any exchange servers within a same Exchange organization.
Symantec's Raptor Firewall has also been identified as another culprit in such cases.

http://support.microsoft.com/kb/295725/en-us