Na minha experiência, a maioria dos servidores de e-mail não verifica o certificado. Eu usei certificados auto-assinados em meus servidores de email para TLS por anos e não vi nenhum problema com a entrega. Então, eu tentaria primeiro e verificaria se os sistemas com os quais você está tendo problemas para se comunicar não funcionam.
O Postfix tem um guia sobre os diferentes níveis de segurança do TLS aqui: link
Os níveis de segurança relevantes que eles podem estar usando são "criptografar", "verificar" e "seguro". Todos eles dizem "Este nível de segurança não é um padrão apropriado para sistemas que entregam e-mails à Internet". Basicamente, os servidores de envio estão fazendo errado. O TLS não deve ser requerido para sistemas de email da Internet. Mas eu suponho que você não tem controle sobre isso.
Se eles estiverem usando o nível de criptografia, um certificado autoassinado funcionará bem.