Turn off wi-fi
I've seen a couple threads on this board regarding this issue on the DX and, being new to it myself, was also having the same issue. ISP blames VZ, VZ blames ISP...still no resolution. Lots of people offering good alternatives like K9, gmail, etc...but what's the point of having this great phone if it can't handle that seemingly simple task of outgoing mail?
After going through the create profile/delete profile ad nauseum, and being lost for better ideas, I decided to turn off the wi-fi. Have no idea if it's even remotely related to the outgoing email issue...but what I can tell you is when I turn off wi-fi, I have absolutely no issues sending email using my roadrunner account set up on the DX, and NOT going through the gmail account, K9 or any other app. I'm assuming you have no issue receiving mail, just sending...those were my exact symptoms as well.