Presumably you're not sending mail from a verizon email address, which would not be blocked. To restate the comments above, Verizon is trying to prevent spam from being sent via hijacked machines within the FIOS network. So if you're not sending mail via a Verizon email server, Verizon assumes you're either a spammer or that your machine has been compromised. Some ISPs will unblock port 25 on request, not sure about Verizon.

It's a tough nut, because if Verizon doesn't block outbound port 25 traffic, then Verizon customers become the most desirable target for the bad guys. And if they do block port 25, they irritate the more sophisticated customers that don't use whatever email address they're assigned by Verizon.

Your VPN solution is ultimately the only surefire way to get your traffic passed at any location. Some networks block by port, but others also use sophisticated "deep packet inspection" technology to actually look for the email dialogue that you have every time you send a message, and they block that dialogue.