Error message: 451 4.4.0 Primary target IP address responded with: “451 5.7.3 Must issue a STARTTLS commnd first” Office 365 Hybrid

In some scenarios you might need to, in your firewall:   Disable Content Inspection with TLS

more about in:

http://www.moh10ly.com/blog/office-365/emails-between-o365-and-on-premises-do-not-work