[VokpAllk]

Бред...
Методом научного тыка и благодаря наводкам аутглюка выяснил, что нас режет контентная фильтрация...
Письма с заголовком FW:, который подставляется автоматически аутглюком, не проходят, а письма с пустым заголовком нормально уходят.
Тему можно закрывать. Это оказывается не наш сервер виноват, а у них слишком жесткие правила на осмысленное составление посланий...
Спасибо за помощь!