Постфикс работает с сертификатами на ура и проблема не в нем, а в сертификатах.

Для нормальной работы с клиентами лучше сделать так:
1. Сгенерить сертификат CA (подписанный сам-собой)
2. Сгенерить сертификат сервера (на CN=fqdn или ip в зависимости от того, как клиенты подключаются)
3. Подписать сертификат сервера сертифкатом CA.
4. На клиентах установить сертификат CA(тот, что без секретного ключа) в корневые.

И все.
Вот подробно про сертификаты тут описано:

http://tldp.org/HOWTO/SSL-Certificates-HOWTO/index.html