Aaaarrrrgh! My server requires a password for outgoing mail, but every time I enter it in iPhone's Mail settings, it reverts back to "Optional" when I leave the screen. As a result, I can't send mail!
This seems to be a known bug. The solution is to first delete all of the outgoing mail settings (server, username). Then fill in the password, then fill back in server and username. Worked for me. See