Problems with Mail Server when IP Address Changes

In an Exchange Server 2003 environment, after the SMTP service is restarted, the Store service is restarted, or the server is restarted, the e-mail recipients may receive old messages that were sent several days before. Or, the e-mail senders may receive Non-Delivery Report (NDR) messages for the delayed e-mail messages that they previously sent.

When this problem occurs, these messages are not visible in the SMTP queues in Exchange System Manager. However, these messages are visible the SMTP Temp tables in the mailbox store. Also, the e-mail senders do not receive an indication that the messages are held by the Exchange Server 2003 server until they receive the NDR messages when one of the services is restarted or when the server is restarted.
When the store starts, the GuidTimestamp is generated on the store side and passed over to Internet Information Services (IIS) store driver (Drviis) through a proxy. However, in some cases, the information that contains the GuidTimestamp is sent to the store driver two times, and IIS receives a different time stamp than the Store receives. When a new message is rendered, the store stamps and submits the messages to the send queue, and then the GuidTimeStamp is changed on the IIS side. Sometimes the messages are not delivered to the next hop on the first try because a remote SMTP host has "Greylisting" enabled. In this case, the SMTP host sends a Temporary Error (4.7.1) message back to the sender that indicates that the sender should retry the transmission of a message in a few minutes. In this scenario, the message is set to a "retry" state by the SMTP service. When the “retry” happens the time stamp on the message is compared with the time stamp of the store driver. When there is a mismatch, the message is considered invalid, and it not delivered until the SMTP service or IIS is restarted.
To summarize, the mail server tried to deliver the messages but reverse dns showed an incorrect address so the mail was not accepted by the remote server and our server sat on it when it was sent information to retry. Because of the timestamp and greylisting (or reverse dns lookup), the message was considered invalid and not delivered until the services were restarted.