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

Во первых конечно же необходимо настроить в принципе саму почтовую систему на сервере — я обычно использую MTA Sendmail или Exim
(непосредственно почтовый сервер на виртуальной машине не поднимаю)

PTR проверка

Далее необходимо настроить соответствие IP адреса сервера-отправителя почты, с обратной доменной записью — так называемая PTR проверка.
Для отладки я создаю простенький php скрипт отправляющий почту средствами штатной фукнции mail() себе же на почтовый ящик gmail и смотрю полученное письмо в исходных кодах («Показать оригинал»)
Received: from srv.mydomain.ru (srv.mydomain.ru. [123.123.123.123])

То есть доменное имя сервера отправителя и обратная запись должны совпадать!
Проверяется с консоли windows
nslookup srv.mydomain.ru
получаем IP адрес 123.123.123.123
далее делаем обратный запрос
nslookup 123.123.123.123
должны получить srv.mydomain.ru

Если несоответствие — необходимо настроить прямую и обратную зону DNS!

Чтобы не ждать пока обновится зона (часа 3-4) рекомендую проверить обратную запись linux командой
dig -x 123.123.123.123 @ns.server.ru
Предварительно узнав какие именно NS сервера обслуживают наш домен командой
whois mydomain.ru

SPF проверка
приведу пример из исходных кодов тестового письма отправленного на гугл
Received-SPF: pass (google.com: domain of info@srv.mydomain.ru designates 123.123.123.123 as permitted sender) client-ip=123.123.12.123;

В переводе на русский — SPF проверка пройдена, IP адрес отправителя считается разрешенным.
Для того, чтобы сервер проходил SPF проверку необходимо IP адрес сервера (или домен) внести в SPF запись зоны (это текстовая DNS запись определенного формата)
Например такой записи «v=spf1 +mx +ip4:123.123.123.123» вполне будет достаточно, чтобы пройти SPF проверку

Далее при настройке почты и изучении оригинала письма мне не понравилась сточка генерируемая моим же sendmail
X-Authentication-Warning: srv.mydomain.ru : bitrix set sender to info@mydomain.ru using -f

видите ли пользователь bitrix не является отправителем для домена srv.mydomain.ru!
Добавляю пользователя bitrix в доверенных пользователей для отправки почты в файл /etc/mail/trusted-users и перезапускаю sendmail — всё, ошибка ушла!

Ну и чтобы не было путаницы с доменными именами, hostname серверу я так же присваиваю srv.mydomain.ru
Правим /etc/sysconfig/network на предмет HOSTNAME=srv.mydomain.ru
и чтоб не ребутить для текущей сессии даём команду
hostname srv.mydomain.ru

Всё!
Обычно этого «набора» хватает для того, чтоб письма нормально доходили и не попадали в спам

P.S.
Бывает нужно ещё и цифровую подпись DKIM настроить для верности — мне не приходилось, но могу порекомендовать хорошую статью по настройке почты (в т.ч. dkim)