A RFC 5321 explica em detalhes como o envio e recebimento de e-mails funciona.
Duas coisas importantes que mencionarei aqui
1) Os e-mails que não podem ser entregues por qualquer motivo (temporário) DEVEM ser enfileirados e tentados novamente mais tarde. Aqui a citação
Retries continue until the message is transmitted or the sender gives
up; the give-up time generally needs to be at least 4-5 days. It MAY
be appropriate to set a shorter maximum number of retries for non-
delivery notifications and equivalent error messages than for
standard messages. The parameters to the retry algorithm MUST be
configurable.
2) E-mail que não pode ser entregue a todos deve ser indicado para o remetente. Aqui a citação:
If an SMTP server has accepted the task of relaying the mail and
later finds that the destination is incorrect or that the mail cannot
be delivered for some other reason, then it MUST construct an
"undeliverable mail" notification message and send it to the
originator of the undeliverable mail (as indicated by the reverse-
path).
Portanto, se todos os servidores de e-mail agirem de acordo com o padrão, não haverá perda de e-mails. Mas dizem que existem alguns servidores de email que não seguem as regras. Neste caso, não deve ser sua responsabilidade aceitar seus e-mails em todos os casos, somente porque eles têm servidores de baixa qualidade.
Eu recomendaria ter um servidor de correio "cold-standby" que você inicializa apenas no caso de um longo tempo de inatividade do Exchange.