Сейчас настраиваю Postix на сервере и столкнулся с такой
проблемой - не принимает письма с gmail. Хотя письма со всех
остальных почтовых сервисов (live, mail, корпоративные, и т.п.)
приходят без проблем.

Gmail возвращает такой ответ:
Google tried to deliver your message, but it was rejected by the
recipient domain. We recommend contacting the other email provider
for further information about the cause of this error. The error that the
other server returned was: 451 451 4.7.1 Service unavailable - try
gain later (state 17).

Сталкивался ли кто с такой ситуацией? Кто может подсказать в
чем может быть проблема?

Установлено: Fedora 8 + Postfix + Dovecot + Spamassasin