This is a normal behavior.
The RFC 1123 states that SMTP server must try to resend messages in the case of delivery failure.
By default Exchange will try to resend failed messages every 15 mins and will quit after 2 days.
(actually first 3 tries are in 10 minute interval). RFC recommends 30 minutes for retries and 4-5 days to quit on the delivery of the message.
i.e.: I send message to [email protected], but SMTP server responsible for domain.com is currently down. Exchange will retry to send the message every 15 minutes and will quit after 2 days (and will send me back NDR – “Non-Deliverable Recipient” message telling that it tried to reach [email protected] and failed.
More details about the correct protocol behavior can be found here:
You can tune the resend interval in the SMTP settings, but Exchange will try to deliver the email after the reboot in any case.