I have just spent several hours narrowing down the problem, 30 useless minutes with someone in Verizon chat support and 20 min on the phone line. All the time was wasted just to find out that Verizon is blocking outgoing connections to port 25. That basically means that you can’t use your own mail servers for sending emails using plain (E)SMTP. The only unblocked server is outgoing.verizon.net.
In fact many ISPs do that in order to fight spamming, but after years of not having this problem with Comcast that was kind of unpleasant surprise.
In my case I needed the external mail server for my webcams (I have whole bunch of them providing security at my place). Fortunately Foscams I use support alternative ports, so I just opened my mail server on an alternative port and reconfigured the webcams. If you’re using postfix, just drop this into /etc/master.cf:
restart the postfix, patch your firewall if necessary