Question : "The object *************" in the message tracking logs can't be found in the directory.  The object may have been deleted.  The tracking history may be incorrect."

Has anyone seen this message before when tracking the delivery of an email to an external address?  I am also prompted with this, "Message transferred to **************** through SMTP" which repeats dozens of times until it times out and an NDR is created.  It looks like most other external email is flowing fine so I think this might be a problem on the other end but I want to be sure.  So far this is happening to one person, and only a few of the many external addresses she uses.  Our system is Exchange 2003.

Answer : "The object *************" in the message tracking logs can't be found in the directory.  The object may have been deleted.  The tracking history may be incorrect."

That means the remote site is behind a Cisco PIX. The Cisco PIX has a feature called SMTP Fixup which attempts to hide the SMTP banner, but instead just causes problems.
It is an issue with the remote site - they need to turn off that feature in their PIX.

If the remote site is not prepared to do that then you need to use an SMTP Connector to route email for that domain via your ISP's SMTP server.

Simon.