Значит следующая беда приключилась с клиентом — не отправляется почта с локального mta, от слова совсем.

Полез в логи, повсюду светилась ошибка вида:

exim R=dnslookup T=remote_smtp defer (-53): retry time not reached for any host или alt1.gmail-smtp-in.l.google.com [$IP] Cannot assign requested address

После краткой диагностики, убедился, что проблема НЕ в dns-ах, т.к. резолвинг в любом виде выполнялся корректно.

В итоге некоторых мучений, с «неговорящей» ошибкой, оказалось, что в файлике:

/etc/exim/domainips

Прописано неверное соответствие domain — ip

Т.е. exim пытался отправить почту для определенного домена с несуществующего адреса, что и приводило к ошибке.