Mailserver: - У тебя статический IP? Динамический = спам. – PTR-запись IP должна указывать на почтовый сервер (mx.yourdomain.com). Если это не так, то велика вероятность попадания в спам-листы. – SPF, необязательно, но снижает шансы попасть в спам-листы. – Почтовый сервер должен отправлять через SMTP с доверенным сертификатом (Let's Encrypt это делает). – По возможности, отправляй только текстовые письма, а не HTML. – DKIM, необязательно, но хорошо бы иметь, не обязательно. – DNSSEC, необязательно, не обязательно.

Проверь, не числится ли твой почтовый сервер в каких-нибудь чёрных списках и убери его. Можно взять подписку у uribl (стоит около 900 долларов в год), а ещё у них есть список антиспама, который можно добавить в чёрные списки Postfix — они не будут блокировать IP твоего почтового сервера. (Они крупнейшие, и все остальные чёрные списки в основном проверяются против них).

Ненавижу uribl за это xD

Однако, первые 2 пункта — самые важные. Весь этот ответ построен по принципу важности, самые первые вещи — самые важные.

Cheers