Владимир Дубровин

Посмотрите в приходящих письмах заголовок List-Unsubscribe, если он присутствует - то в нем есть ссылка на отмену подписки.

В Google Chrome поддержка push-нотификаций появилась совсем недавно (в Chrome 42), в Gmail она уже доступна в Mail.Ru поддержка тестируется, пользователям будет доступна в ближайшее время.

Почта перестала доходить, потому что для домена mail.ru включен DMARC, защищающий письма от подделок:
https://habrahabr.ru/company/mailru/blog/282602/

Обычные редиректы не должны менять содержание письма, а значит не должны портить DKIM-сигнатуру и DMARC в такой ситуации не мешает прохождению письма. Бывают ошибки типа https://support.microsoft.com/en-us/kb/2993556 которые Microsoft устраняет, попробуйте установить последние сервис паки и rollup update'ы.

Возможно именно в вашей конфигурации по каким-то причинам письмо перестраивается, например в настройках формата стоит принудительное изменение формата на RTF/HTML. Я не силен в настройках Exchange, но проверьте чтобы этого не происходило. Попробуйте отправить письмо с любого другого адреса на получателей на обеих серверах, сравните diff'ом результат, чтобы понять, почему бьется DKIM.

И имйте ввиду, что если бьется DKIM-сигнатура письма, значит вы не получаете письма не только от mail.ru, но и от yahoo, aol, linkedin, facebook, Вконтакте, paypal и много кого еще, включая письма от самого гугла (@google.com) - т.к. на всех этих доменах тоже строгий DMARC.

Посмотрите в сторону pdd.yandex.ru / biz.mail.ru / apps.google.com - это гораздо проще, чем обслуживать свой сервер.

Рекомендации, в т.ч. по верстке, есть здесь.

Так а зачем проверять домны до рассылки? Проблемы могут быть временными/разовыми, например забыли вовремя продлить домен. Сконфигурируйте максимальное время доставки в MTA, ловите отбои от почтового сервера (для этого желательно каждому получателю формировать отдельное письмо с уникального адреса отправителя в envelope-from). Если вы получили, например, 3 отлупа на последние рассылки - убирайте пользователя из списка. Ящики могут "умирать" даже на живых доменах.

Странное у вас письмо, интересно как вы его сформировали.
У вас фейлится не SPF, у вас фейлится DMARC для домена gmail.com. Фелится DMARC потому что письмо не подписано DKIM, хотя отправлено через веб-интерфейс GMail'а. А DKIM оно не подписано скорей всего потому, что From: сформирован с ошибкой.
From: "mygmail@gmail.com"
там не должно быть двойных кавычек. Или
From: mygmail@gmail.com
или
From: "My Name" <mygmail@gmail.com>

P.S. А SPF mydomain.com на это письмо вообще никак не влияет, т.е. SPF проверяется для домена gmail.com и вашего IP там, разумеется нет, он всегда будет фейлится на перенаправлении если вы адрес конверта перезаписывать не будете.

Можно было бы использовать
www.athensfbc.com/imap_tools/details.html
с опцией -z, но IMAP SEARCH мало где поддерживается а без него не уверен, что получится. Если ящики не очень большие, можно попробовать настроить сбор почты в один ящик (например со 100 ящиков в 10 и с этих 10 в 1) и поискать в результирующем ящике.

У multipart/mixed не может быть Content-Transfer-Encoding.
После каждого заголова должна идти пустая строка - перед
$headers .= "This is a MIME encoded message." . $eol;
перед
$headers .= $message . $eol;
и перед
$headers .= $content . $eol;
После конечного сепаратора - тоже.
Строки должны разделяться CRLF, PHP_EOL в Linux это просто LF.
Если это не поможет - опубликуйте конечный eml.

У вас настроен лимит на размер подписываемого содержимого (l=366) и этот лимит конфликтует с размером ключа. Уберите этот лимит, его использование крайне нерекомендуется.

P.S. временную метку (t=) я бы тоже рекомендовал убрать из подписи, иначе можете получать ошибки если у вас часы будут вперед хотя бы на секунду относительно получателя.

P.P.S. и нормализацию используйте relaxed/relaxed, меньше проблем будет.

Попадание в спам не зависит от интенсивности отправляемых писем, зависит от качества писем и правильности оформления. Вот здесь мы собрали технические рекомендации + убедитесь, что вы соблюдаете основные требования к массовым рассылкам.

Возможно три варианта:
1. IMAP-сервер создает эти папки во входящих для новых пользователей, тогда надо смотреть конфигурацию IMAP-сервера.
2. IMAP-сервер вообще их не создает по умолчанию и они создаются почтовым клиентом, которым вы первым заходили в этот ящик по IMAP, скорей всего это был Thunderbird, т.к. он создает эти папки по-умолчнию именно как подпапки входящих.
3. IMAP-сервер создает папки, но названия отличают от тех, которые "любит" Thunderbird (например название папки Trash для удаленных). В таком случае Thunderbird так же создаст папки, но помимо них будут еще папки созданные IMAP-сервером с другими названиями.
Исправить это можно через свойства учетной записи (Параметры/Параметры сервера для удаленных и Параметры/Копии и папки для остальных папок). В Outlook есть соответствующая настройка. Mail.Ru подхватывает имеющиеся папки, чтобы применить изменения в папках можно удалить эккаунт через https://account.mail.ru/user/delete и войти по-новой.