> обратная зона у вас настроена? Проверте свой ай-пи в спам базах.

ptr настроена. Не у меня, а у хостинга (smtp - vps), но не суть - уже проверял, все ок. Сейчас посмотрю, где проверить на присутствие в спам-листингах. Спасибо!

Добавил: проверил через 2ip.ru. Все ок, нигде меня нет.

Добавил2: у меня есть второй smtp, тоже vps, но в другом хостинге. Через него все ок. Т.е. проблему, возможно, надо искать у меня?

> Полный лог покажи

1 relay postfix/smtpd[28801]: warning: 215.132.165.123: hostname <client_router_hostname> verification failed: Name or service not known
2 relay postfix/smtpd[28801]: connect from unknown[215.132.165.123]
3 relay postfix/smtpd[28801]: 22A4924631: client=unknown[215.132.165.123], sasl_method=DIGEST-MD5, sasl_username=my_email@hostname
4 relay postfix/cleanup[28810]: 22A4924631: message-id=<!&!AAAAAAAAAAAYAAAAAAAAAIcZxIrfYNdHpVrt4z9mJQBigwAAEAAAABAhhQ9rxRtArcU8Wal6FhYBAAAAAA==@hostname>
5 relay postfix/qmgr[28793]: 22A4924631: from=<my_email@hostname>, size=4367, nrcpt=1 (queue active)
6 relay postfix/smtp[28814]: 22A4924631: to=<email_to@receiver.com>, relay=mx.receiver.com[128.42.72.17]:25, delay=0.49, delays=0.26/0.01/0.14/0.07, dsn=5.7.1,
      status=bounced (host mx.receiver.com[128.42.72.17] said: 554 5.7.1 <my-server.hostname>: Helo command rejected: Access denied (in reply to RCPT TO command))
7 relay postfix/cleanup[28810]: 921B624648: message-id=<20150820085133.921B624648@my-server.hostname>
8 relay postfix/qmgr[28793]: 921B624648: from=<>, size=6311, nrcpt=1 (queue active)
9 relay postfix/bounce[28815]: 22A4924631: sender non-delivery notification: 921B624648
10 relay postfix/qmgr[28793]: 22A4924631: removed

Как я понимаю:
1,2 - ip, с которого я пишу письмо, не найден в mynetworks.
3 - Прошел проверку с именем my_email@hostname
4,5 - подготавливается письмо к отправке.
6 - при отправке удаленный сервер mx.receiver.com не принимает мой сервер
7-10 завершается соединение, письмо удаляется из очереди.

Дальше в логе (не стал приводить) идет пересылка ответа (то, что я получаю в ответ):

... Бла-бла-бла
host mx.receiver.com[128.42.72.17] said: 554 5.7.1
    <my-server.hostname>: Helo command rejected: Access denied (in reply to RCPT
    TO command)

Вроде ничего не упустил.

> Рассылками не занимаетесь? Как выглядит ваш HELO - сколько в нём точек
> и/или цифр? Может в нём есть что-то похожее на IP или
> слово dynamic/adsl/client и т.п.?

Рассылками, естественно, не занимаюсь. Тут и говорить не о чем.

Если HELO - это то, что видно если сделать telnet на 25 порт, то вот:

220 my-server.hostname ESMTP Postfix

(вместо my-server.hostname стоит нормальный домен).

Тут вряд ли злой умысел, скорее совпадение не очень нормальных настроек плюс что-либо из антиспама необычного на принимающей стороне. Я написал запрос и менеджеру, с кем работаем, и, по его ответу, в тех. поддержку мол давайте решим проблему. И тишина. Вот и долбаю со своей стороны. Про получателя ничего не знаю, что у них и как. Проблемы с ними уже были как-то.