Depois de muitas horas tentando entender, incluindo a depuração nos processos smtp e tlsmgr no master.cf, consegui determinar que o FIPS desabilitando o md5 era realmente o problema. Adicionando o seguinte ao master.cf corrigiu o problema:
smtp_tls_fingerprint_digest=sha256
A configuração para sha1 e sha512 também funcionou. Observe que a documentação do postfix avisa sobre a configuração de algo diferente de sha1 ou md5 (sendo o padrão md5). Da documentação:
While additional digest algorithms are often available with OpenSSL's libcrypto, only those used by libssl in SSL cipher suites are available to Postfix. For now this means just md5 or sha1.
No entanto, para minhas necessidades, o sha256 parece estar funcionando bem.