A customer of mine has a Hybrid Exchange environment. It recently moved from one ISP to another and mail stopped flowing.
DNS, firewall and NAT rules have been updated. The customer waited for long enough for the DNS to propagate. Still no joy.
What was missing? Searching the Internet returned no meaningful results.
For those of you who are going through the same experience, once you moved to the new ISP, updated your DNS records and changed your firewall and NAT rules, simply re-run the Hybrid Configuration Wizard to populate configuration items with the new details to restore functionality.
The same applies when the public IP address changes, regardless of the reason.
Have a nice day :-)