This is very strange as our server does not use TLS. Neither have I configured Joomla SMTP to use TLS.

Your mail server is advertising TLS support (via STARTTLS). PHPMailer library is then turning on secure connection, which is failing because the certificate is not valid. Your mail server needs to stop advertising TLS support or provide a valid certificate. This is called Opportunistic TLS and was recently introduced into PHPMailer library in version 5.2.10. You can find more details regarding this below.

github.com/PHPMailer/PHPMailer/wiki/Troubleshooting#opportunistic-tls

FYI, PHPMailer works. But not ideal as the mails go straight to spam.

That's something you'd need to address with your host as I've no idea why they're going straight to spam, but likely the result of your mail server domain being blacklisted.

We use Fabrik, Jomres, Virtuemart and various other platforms on different websites on the same server with the exact same mail setup. We've never had any issues. It does not make sense that it should now be different with CB if CB uses Joomla to send mail?

Joomla specifically implemented a workaround to force off Opportunistic TLS, because incorrectly configured mail servers will run into your issue. Some extensions flat out turn off verify_peer as well creating a security vulnerability by disabling secure connections entirely.

You maybe able to workaround this by explicitly disabling TLS by setting "SMTP Security" within Joomla global configuration to "SSL/TLS" forcing it to SSL.