В общем, более внимательной изучение почтового лога показало достаточно известную проблему. В принципе, это правильное, когда-то, поведение почтового сервера, только вот, в наше время, его уже надо избегать.
1. Постфикс принимает сообщение для пользователя домена и оно попадает в очередь.
2. Начинают работать всякие фильтры, может быть пользователя не сущестует и т.п. В какой-то момент принимается решение не доставлять сообщение.
3. Правильный почтовый сервер обязан сформировать боунс отправителю.
И вот она, проблема. Спаммер использует в mail from чужие E-Mail, сервер формирует по ним спам из боунсов.
Фактически, требуется перенастроить сервер так, чтобы все проверки проходили до попадания в очередь и Postfix, при необходимости, выдавал 5xx на этапе получения сообщения. В этом случае проблема боунса будет проблемой сервера отправителя. Другой путь - не формировать боунсы, но это совсем плохой путь.