I have had the same issue w/ verizon for a number of weeks. I can only receive mail, and sending is spotty at best. I generated new accounts to no avail, spent friutless hours on the phone with the Verizon Braintrust, and had two trips to the Genius bar at my local Mac store. What I finally learned is that "Verizon doesn't officially support the Macintosh Mail software". This from the genius bar. Apparently it is not a new problem, and there are plenty of folks with the same problem. My account worked fine for my first 3 years of DSL w/ Verizon, but only in the past few months has this been such a problem. I am now on my 2nd Macbook pro, and am still having the same problem. My guess is that somebody upgraded software in the chain, and didn't care to make it compatible with the other...?
If anyone has resolved this problem, I would love to hear about it- as I am about to ditch Verizon for a different DSL provider.