На одном из серверов вся почта попадала в папку спам на gmail. Решить проблему с попаданием в спам никак нет возможности, поэтому было принято решение по отправке почты через relay. Сама настройка оказалась простой, но времи на поиск решения я потратил прилично.
1. # cd /etc/mail

2. Редактируем файл ./sendmail.mc, находим в нем фразу с SMART_HOST и заменяем на:

dnl define(`SMART_HOST', `mail.example.com')dnl
define(`SMART_HOST',`[mail.example.com]')dnl

где mail.example.com — доменное имя вашего релея.

3. Обновляем конфигурационный файл:

#m4 ./sendmail.mc > ./sendmail.cf

Если не найдется команда m4 то устанавливаем её:

yum install sendmail-cf

4. Перезапускаем sendmail:

# /etc/init.d/sendmail restart
Останавливается sm-client:                                 [  OK  ]
Останавливается sendmail:                                  [  OK  ]
Запускается sendmail:                                      [  OK  ]
Запускается sm-client:                                     [  OK  ]