Cannot validate Exchange Online connectors to On-premise exchange in a 365 Deployment

Hi Everyone,

I was wondering if anyone can help or advise? Unfortunately I feel i'm running out of ideas at the moment and so If anyone can help it would be very much appreciated

Recently I've setup an 365 hybrid deployment with exchange 2013 to use AD SSO for our VLE and to gradually move over our organisations users and decommission the exchange server.

Unfortunately I'm having difficulties getting the the Exchange Online connectors to communicate correctly with our on-premise. After using the Hybrid Deployment wizard the connectors are setup automatically but point to our council/ISP TMG server. As the connectors require a direct connection I have asked them to setup a public IP/address for our on-premise exchange server for the connector to use. When trying to validate this connector I receive the error log:

450 4.4.317 Cannot connect to remote server [Message=451 5.7.3 STARTTLS is required to send mail] [LastAttemptedServerName=*server*] [LastAttemptedIP=*ip*] [*EUR02.prod.protection.outlook.com*]

There are Cisco routers but I have been advised that no SMTP inspection is taking place between any of the routers. Using telnet on my desktop to our on-premise shows that STARTTLS is there but when trying it from our Offsite backup server it shows the following:

250 - *on-premise exchange* hello [IP]
250 - SIZE 104857600
250 - PIPELINING
250 - DSN
250 - ENHANCEDSTATUSCODES
250 - 8BITMIME
250 - BINARYMIME
250 - CHUNKING

We have a Sonicwall NSA3600 firewall and I've gone through it with an engineer checking any security services that may be preventing it, I've updated firmware and turned off Deep Packet Inspection briefly on the chance it was the firewall but there are no settings I believe that are causing the issue.

Can anyone help/advise?

Thanks

Marc