I have searched the Interent over for a solution to this problem. My error message lists Port 25 as the problem.
I use Windows Mail and McAfee antivirus software. I've gone into the virus software and unblocked Port 25. I have also changed my email addresses to Port 587 as recommended by Verizon but that didn't work either.
I have several email accounts included Verizon and other accounts that work fine with Port 25. I only have one that is not working with Port 25.
There might be two settings in your anti-virus software: blocking connections to port 25 on your computer and blocking connections to port 25 on an outside computer. Your mail program needs to connect to port 25 on outgoing.verizon.net. This is an authenticated server and you need to use your Verizon Online username and password. Note: you don't automatically get a Verizon Online username and password when you sign up for FiOS. I had to call yesterday to get one.
If you're using something like outlook or outlook express, also make sure that on the outgoing settings that you check the box that says "my outgoing server requires authentication". And make sure that the "use secure password authentication" is not checked.