Ugh, reminds me of my days in web hosting tech support We were always to blame when ISPs blocked outgoing SMTP.

You might want to check for different types of authentication... some of them require you to log in to the POP server first. I think Verizon might require SMTP authentication with your verizon user/pass (at least according to a possibly outdated document I found by searching).