Test your email server encryption

On the other hand, simply providing this service enables anyone, malicious or not, to determine if a given mail server is vulnerable. Publishing a "shame list" doesn't reveal any new information, but may result in improvements to the vulnerable servers as a result.

I agree, it's also not that great to have a list of "Insecure web servers" [0], there should be a "don't show checked site in public results" checkbox like on ssllabs.com's certificate tests.

[0] https://ssl-tools.net/webservers

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.

To be fair it should say unknown rather than insecure if the secondary can't be accessed and it can't confirm that it is secure and you should assume an attacker able to perform a Man in the Middle attack on you could disrupt your traffic sufficiently to force the fallback to to the secondary server.

Although does the validity of the incoming mail servers certificates actually matter? In an ideal world other hosts would never send to improperly signed hosts or without TLS but that clearly is not the case so I'm not sure what current practical value having proper certificates actually has. In the longer term by pushing people to adopt proper certs it may become practical for people to turn off sending to servers without proper certificates so this may be better seen as part of a long term effort.