One of the prerequisites for having a Hybrid relationship established between your on-prem Exchange environment and Office 365 is to have a functioning mail flow using TLS. The Hybrid Configuration Wizard automatically creates the inbound and outbound connectors required both in your on-prem environment and in Office 365 as a part of the setup, and this is used for secure mail transfer between the two environments.
If TLS fails your mail flow will suddenly stop, and outgoing emails are stuck in the queue with error message 451 4.4.0 Primary target IP address responded with: “451 5.7.3 Must issue a STARTTLS command first.”. You may not even be able to complete the Hybrid Configuration Wizard, you just get an error message stating that Subtask ValidateConfiguration execution failed: Configure Mail Flow.
Several blogs on the Internet addresses these problems, but must of them show you the commands how to turn TLS off. This is not something that I recommend! A problem is not solved by hiding it’s symptoms, always try to find the root cause.
There are several possible reasons for malfunctioning TLS. A good start in the troubleshooting is to use good old telnet.exe and connect to smtp.office365.com on port 25. By simply sending the ehlo command you can easily see if the server is accepting TLS connections. If you get a 250-STARTTLS response the problem is most likely with your certificate. It may not be configured to be used with SMTP, or is longer valid. Also make sure that you have installed the latest Root Certificate Updates from Windows Update.
A response from the SMTP server without the STARTTLS extension listed might indicate that your IP address is on a blacklist. Use one of the online tools available for free to check the status of your IP address. In your telnet session you will find the IP address you are connecting from.
This IP address must also be in list of Sender IP Addresses in the Hybrid Mail Flow Inbound Connector in Office 365 created by the Hybrid Configuration Wizard. If it isn’t there it must be added. If the IP is incorrect the connector will not be used, and the mail flow will use the MX record instead, without enforcing TLS.
Another result from your telnet session could be this:
In this case a firewall is configured to filter some protocols, which effectively stops all TLS communication. In for example Cisco firewalls the solution is to turn off ESMTP inspection.
This is not a complete guide on how to solve your TLS problems, but it shows some common solutions, and hopefully it gives you some input to start your troubleshooting.