charon

по-хорошему ящик надо удалять. Что значит не комильфо? Это рабочий ящик, рабочего нет — нет ящика. Предполагается, что перед увольнением сотрудник передаст все контакты замещающему его человеку и тот найдёт способ известить всех нужных людей о том, что теперь адрес надо поменять.
Могу вас заверить, что большинство уволившихся сотрудников никогда не заходят в свой бывший ящик, даже если он работает и пароль не изменился. Поэтому информация там просто лежит и плесневеет.

простите, недочитал.

Уточняю, что MX-записи моих доменов указывают на mx.yandex.ru., поскольку я использую ПДД Яндекса для получения писем.

DKIM и SPF должны быть настроены с учётом того, откуда вы почту ОТПРАВЛЯЕТЕ, а не откуда получаете.

Правильно ли я понимаю, что если у меня на одном IP-адресе расположено несколько сайтов (поскольку они на одном сервере), то PTR я смогу настроить только для одного из них?

да

Что ещё можно покрутить в настройках exim4, DNS, чтобы письма не попадали в спам (а то сейчас они у меня на Яндексе и Гугле даже в спам не попадают)? Про DKIM в курсе, а что ещё? EHLO или ещё что-нибудь?

DKIM и SPF достаточно.
EHLO? А разве раньше вы этого не сделали? В EHLO надо отдавать то же, что прописано в PTR.

и конфига кусок. Секцию routes

бесплатная даже если и есть, я бы всё равно посоветовал отдать эту задачу профи типа Амазона. Ну если надо только бесплатно, то не забудьте поговорить с вашим админом.

лично я бы начал с того, что запросил у sendgrid.com полный лог рассылки. По идее, они должны его предоставить. Посмотрел бы на него и выделил ответы почтовых серверов, куда письма недошли. И дальше по обстоятельствам.

В разных статьях на эту тему я видел обычно 2 ответа: Mozilla Thunderbird и Windows Live Mail. Последний — единственный, который нативно поддерживает 64 бита.

написать хостеру — пусть закроет ящик. Я закрывал желающим в своё время.

чтобы не портить отношения со спамлистами лучше использовать XMPP и слать сообщения в свой джаббер :) Джаббер-сервер может логировать определённые сообщения.

вам надо как-то отучить вашу CMS вставлять 5-ый аргумент.
В доке codeigniter.com/user_guide/libraries/email.html написано, что есть возможность в конфиге config/email.php (по умолчанию не существует) задать настройки отправки почты. В т.ч. можно сделать отправку через SMTP-соединение, а не локальный почтовый сервер.
Попробуйте пойти этим путём.

я как бывший суппорт хостера с проблемой знаком. У нас почтовиком был exim. Суть происшествия в том, что почтовый сервер запрещает подставлять в поле Sender любое имя, а только то, от кого запускается процесс (РНР). Также можно включить разрешение такой подстановки, но лично я бы на сервере массового хостинга этого не делал. Такой запрет помогает отслеживать спаммеров и взломанных клиентов. А вот на ВПСах и колокейшене часто отключали такую проверку.

в настоящее время ведущими компаниями ведутся работы по решению вашего вопроса. Насколько я знаю, Яндекс и Хотмэйл уже сортируют уведомления от сервисов и показывают их как-то особенно. Поэкспериментируйте с этими двумя. Думаю, Гугл тоже что-то придумает скоро.