If you receive a non-delivery report (NDR) from a remote SMTP e-mail domain, and the e-mail address is valid, it may be that the remote site is not RFC-compliant.
When Exchange Server connects to a remote SMTP server, it will send multiple messages (if queued) during a single session. If the remote site is not RFC 821 compliant (section 4.1.1), it may reject the 2nd - nth message.
If you don't have control of the remote site, you can set the Internet Mail Service to only send a single message per remote connection.
NOTE: This is a global setting that will affect performance.