TLS шифрование почты (команда STARTTLS) поддерживается в sendamil начиная с версии 8.11, в статье доступно рассказано как включить поддержку TLS шифрования почты.

<pre>

# Генерируем ключи
mkdir /etc/mail/certs
cd /etc/mail/certs
openssl dsaparam 1024 -out dsa1024.pem
openssl req -x509 -nodes -newkey dsa:dsa1024.pem -out mycert.pem -keyout mykey.pem
rm dsa1024.pem
chmod -R go-rwx /etc/mail/certs

# Правим m4 конфиг для sendmail
define(`CERT_DIR', `MAIL_SETTINGS_DIR`'certs')
define(`confCACERT_PATH', `CERT_DIR')
define(`confCACERT', `CERT_DIR/mycert.pem')
define(`confSERVER_CERT', `CERT_DIR/mycert.pem')
define(`confSERVER_KEY', `CERT_DIR/mykey.pem')
define(`confCLIENT_CERT', `CERT_DIR/mycert.pem')
define(`confCLIENT_KEY', `CERT_DIR/mykey.pem')

</pre>

URL: http://www.citi.umich.edu/u/provos/sendmail.html
Новость: https://www.opennet.ru/opennews/art.shtml?num=2251

• Настраиваем sendmail для передачи почты в зашифрованном виде,Аноним, 13:06 , 20-Мрт-03
• Настраиваем sendmail для передачи почты в зашифрованном виде,Ilia, 14:35 , 20-Мрт-03
• Настраиваем sendmail для передачи почты в зашифрованном виде,Аноним, 03:31 , 21-Мрт-03
• Настраиваем sendmail для передачи почты в зашифрованном виде,Paul, 10:22 , 01-Апр-03

А с другими хостами связь как будет поддерживаться, им обязательно ключ иметь?

Необязательно. Но если ключа у них нет, в логе будет пометка FAIL, примерно так:
Mar 20 14:00:11 ims sendmail[49660]: STARTTLS=server, relay=mail@mail.mydomain.dom [111.222.333.444], version=TLSv1/SSLv3, verify=FAIL, cipher=EDH-DSS-DES-CBC3-SHA, bits=168/168

Тогда только есть смысл делать только для клиентов.
А можно к примеру включить в sendmaile такую опцию что
relay работает только при наличии сертификата? ;)

Яндекс поддерживает защищенное соединение, а это уже достаточно для того, чтобы включать оное на своем релее.