I don't know if anyone is still have problems sending Verizon email from their Iphone, which this may help, but I just signed up a new internet account with Verizon also setting up email on my I-phone and ran into the same problems on outgoing mail as a lot of people seem to have done. After googling, changing port settings etc with no luck, I noticed on the outgoing SMTP setup tab, password line, I phone automatically entered my full xxxxx.verizon.net address, not just my username. Changing this to just the username fixed the problem. It doesn't seem to matter what the outgoing port setting is but I set it back to 25.
This may be redundant but I thought I would advise,