Verizon refuses my outbound emails, so far from two public wifi locations away-from-home. One is a Comcast ISP location. Never refuses them from attwifi locations, however. Inbound emails are not affected anywhere, and internet usage is not affected. An automated refusal is all that I get. How about providing some information, so I hate you less for being an overblown, unresponsive, too-big-to-fail provider? Like, can I change a setting?
Are you configured to use ssl and smtp port 465, pop port 995? Smtp Port 25 is usually not accepted unless you are within the Verizon network.