Storing emails elsewhere when Exchange server goes down

the server does not support TLS via the STARTTLS command

There's your error...so it would seem that your Exchange server isn't setup properly for TLS.

1. Telnet to the Exchange server on port 25

2. Enter ehlo, If “250-STARTTLS” is listed in the response, Opportunistic TLS is offered.

If not, you'll need to enable TLS on the receive connector:

Set-ReceiveConnector “ReceiveConnectorName” –DomainSecureEnabled $true –AuthMechanism TLS

However, understand what you are doing first, as the Receive connector might be used for other inbound traffic and it won't FORCE TLS so read the following Technet article FIRST!

See here for more information on setting up mutual TLS on Exchange: http://technet.microsoft.com/en-us/library/bb123543.aspx

Otherwise you can disable TLS in MSMTP if you'd like.

Microsoft don't use the public blacklists, they have their own - so checking blacklists online was a waste of time.

You need to ensure that the server is setup correctly for sending email. The fact that it is not your primary email server makes no difference. That means the server needs to be on a static IP address, with a matching A record and PTR pointing to that IP address. The FQDN on the Send Connector also needs to match that A record.

The other option would be to setup Exchange to relay the email through the server in the data centre. That would mean setting up relaying on that server and then configuring it as a smart host in Exchange.