Сервер и почта.

Проверьте, прописана ли обратная зона для ip-адреса почтового сервера, прописаны ли spf в dns для домена из адреса отправителя.

Убедитесь, что письмо формируется в соответствии с RFC.

Если всё в порядке, а письма всё равно не приходят (попадают в спам), то скорее всего, у гугла предвзятое отношение к вашему ip или всей подсети. Он очень привиредливый.

Если письма вообще не приходят, вам должен возвращаться отлуп с объяснением причин.

на гмаил вообще не доходит. Письма с объяснением тоже не присылаются.

смотрите логи

Но мне кажется не в этом дело. Мб ip в бане?

Не эти логи - почтовые. Дай угадаю следующий вопрос: "иде это?".

да. где это

Как правило все логи хранятся в /var/log/

Я бы начал с пробития IP по черному списку

Mail.ru последнее время очень строго проверяет соответствие RFC, другие иногда игнорируют.

Если туда идут, то вероятнее всего вариант от Andreyka

Чтобы не гадать - скажите что за операционная система у Вас установлена, какая версия? Какой почтовый сервер для отправки используется (sendmail, postfix и т.п.)?

Посмотрите в /etc/syslog.conf (или /etc/rsyslog.conf) - в какой файл направлены сообщения почтовой системы (mail.*).

Тоже "песатель"? ТС ясно и недвусмысленно выразился: