I guess that you simply pointed mail.example.com to www.spamfirewall.at? I would expect your setup to work if you'd instead point your MX record at www.spamfire

I guess that you simply pointed mail.example.com to www.spamfirewall.at? I would expect your setup to work if you'd instead point your MX record at www.spamfirewall.at, so that the certificate will match what the sender expects to see. IIRC, SpamAssassin (slightly) penalizes e-mail coming from anything except mail.example.com and smtp.example.com, so it would be preferable to get your mailserver to use mail.example.com with an appropriate certificate. But if this is indeed an external service, you may not want to give them the private key of a mail.example.com certificate. In any case, it's worrying if they're vulnerable to Heartbleed, but it's not that bad if SSL doesn't work - mail will still be sent in plaintext if the sender's mail server does not support it, or if you're actually under (man-in-the-middle-)attack, so you should treat e-mail as fairly untrusted anyway.