[cameron]

Все, что я почерпнул из логов - это то, что письма с нашего ip-шника отфутболиваются как спам. »

это следствие.

Что я упустил? »

- разбор лога smtpIN, что бы убедиться что там ваши клиенты.
- проверку телнетом на открытый релей.
- счётчики сообщений, быть может у вас есть учётка test с паролем 123 - её сбрутили.
- посещения зенхауса и втаптывание своего ИП в формы проверки - иногда там есть причины бана.
- анализ логов шлюза на предмет большого smtp out траффика, как временная мера- запрет исходящего наружу смтп и разбора лога дропнутых пакетов.
это очевидное из первоочередного.