akelsey

Два статических ("белых") IP адреса на разных каналах. Их обоих с разными приоритетами в МХ записи DNS. Всё будет работать так как вы хотите.

Проверять ежеминутно процесс по крону, и если не доступен -гасить Exim с уведомлением админа любыми способами, exim недоступен, храниться почта на транзитных серверах или серверах отправителях, всё починили, запустили Exim - почта пришла получателям.

Искать почтовый сервер с функцией Catchall, простейши и бесплатный под Win есть hMailServer например.

Больше всего похоже на greylisting, необходимо его отключить для вашего исходящего домена (обычно у него стоит автообучение, если он уже принимал с этого адреса письма, то как бы и не должно, но мало ли кто-там его до вас настраивал).

купить впску (лучше две) по доллару за месяц, настроить там postfix/exim/sendmail по вкусу и эксчи натравить на смарт-хост
PS
Либо попросить провайдера открыть рилей с их почтового сервера.