I guess I should have clarified where the "unsent email" notice comes up. It comes up at the bottom of the screen in the gray box after I get connected. I do not have an "outbox" that shows unsent emails.
These mails just hanging there - you'll have to look up the SMTP settings where you're sending from -> outgoing mail server. Go check your providers website for these settings and go trough them on your iPhone account.