Rsa97

Ключ точно находится в TXT-записи dkim._domainkey.ваш.домен?

Можете. Но вероятность, что они не дойдут до получателя заметно повышается.

Потому что по стандарту заголовки письма (From, To, Subject, ...) могут содержать только печатные символы из ASCII-128, то есть с кодами от 0x20 до 0x7F.

Дык английским же по белому написано - MX.

От того, что вы перенесли сайт не другой хостинг, домен сайта не изменился, значит и настройки в DNS менять не надо.
Измениться может набор функций, доступных на хостинге. Смотрите логи своего сайта на предмет ошибок.

adlab.ee - это ваш домен?
Если да, то проверяйте настройки SPF, DKIM и DMARK.

Никак. SPF, DKIM и DMARK не зря придумали.
Сегодня вы отправляете почту от адреса какого-то пользователя, завтра спаммер отправляет почту от вашего адреса.

Relay access denied - доменная часть адреса не находится в списке доменов, для которых разрешена пересылка почты и почта пришла не из локальной сети сервера.

А с чего вы взяли, что по адресу 94.100.178.70 есть доступный снаружи DNS-сервер?

# dig NS mail.ru
;; ANSWER SECTION:
mail.ru.                370     IN      NS      ns1.mail.ru.
mail.ru.                370     IN      NS      ns2.mail.ru.
mail.ru.                370     IN      NS      ns3.mail.ru.
;; ADDITIONAL SECTION:
ns1.mail.ru.            596     IN      A       217.69.139.112
ns2.mail.ru.            596     IN      A       94.100.180.138
ns3.mail.ru.            54      IN      A       185.30.176.202

Интерпретация локальной части почтового адреса полностью зависит от сервера. Никакими стандартами она не оговаривается. В зависимости от настроек, в локальной части адреса точки могут как игнорироваться, так и использоваться, она может быть регистрозависимой или нет.

А имя корректно в заголовок вписано, перекодировано в ASCII-7?

1. Нет
2. Не обязательно, но крайне желательно.
3. A-запись в DNS, PTR-запись у провайдера.
4. Если у организации есть лишние деньги.

С юридической стороны

влечет наложение административного штрафа на граждан в размере от двух тысяч до двух тысяч пятисот рублей; на должностных лиц - от четырех тысяч до двадцати тысяч рублей; на юридических лиц - от ста тысяч до пятисот тысяч рублей.

С технической - чревато попаданием в спам-листы.

Для начала вам надо убедиться, что все серверы, через которые пойдёт письмо, поддерживают UTF8SMTP согласно RFC5336. В противном случае в поле From русский адрес указывать нельзя.

Настроить fail2ban

У вас для вложенного файла стоит Content-Type: multipart/mixed;
То есть, вы говорите, что эта часть письма сама состоит из подчастей.
Замените на Content-Type: image/jpeg; charset="utf-8";

1. В заголовках письма, в том числе Subject (который у вас почему-то назван $pagetitle) допускается присутствие только символов из ASCII-128. Все остальные, в том числе и русские буквы, должны быть закодированы согласно RFC2047.
2. Заголовок From должен содержать реальный адрес отправителя и, опционально, его имя согласно RFC2822
3. Заголовки должны разделяться комбинацией \r\n (CR LF). Между этой комбинацией и началом следующего заголовка не должно быть пробелов.

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