First off, check your sent for messages being sent out. Delete it if you can, and the message should stop appearing when you first open Mail.
Next, I'm assuming this started happening after the 2.0 update? This seems to be the case for this issue. I have ran into this twice now and both were after the 2.0 update.
Assuming you updated, try to remember if you had to reenter your email information manually on the iPhone again. If you did not, then it may have been backed up and re-synced to your iPhone automatically. With the current bugs, it'll be best to set up the account manually.
+NOTE: Steps 1-4 may not be necessary. You may try step 5 first and if it doesn't work, perform the entire process.+
The fix I found:
*1. Delete the account on the iPhone.*
Before doing this, be sure you know your settings to recreate this account. If it is one of the prebuilt email addresses (Gmail, AOL, Yahoo, MobileMe, etc), the account settings won't be an issue. If you are using a POP or IMAP account other than the ones built in, contact your email provider for account settings, or, alternatively, look in the Mail Settings on the iPhone before you delete it or online. Some settings include incoming and outgoing server host names, port numbers, whether SSL is used, and authentication type. Don't forget your username and password too!
This may help some of you.
http://www.apple.com/support/iphone/mailhelper/
*2. Once deleted, recreate account*
Enter Settings > Mail, Contacts and Calender > Add Account
*3. Once created, test to see if you receive mail.*
If not and you did before deleting the account, look into your settings, something may have been missed
If it works, continue to the next step.
*4. Check to see if issue still exists.*
Compose a new message AND reply to one
If it works, great. If not continue on.
*5. Enter your Username and Password for your OUTGOING MAIL SERVER*
This is the step that fixed the issue both times when I ran into them.
Go into Settings > Mail, Contacts and Calendar > +Your Account+ > Tap the Outgoing (or SMTP) Server > Tap Primary Server > Enter Your Username and Password in the Optional fields.
Username is usually the first part of your email address (everything before the @) or it can also be your entire email address. Password is the one you'd use to log into its webmail.
Usually, these "optional" fields are truly optional. In this case, having them filled in fixed the issue.
Actually, fixed it twice. Lastly, a hard reset (hold home and power button until screen goes completely off, ignore slide to power off) and a restore are other two options at the end.
Hope this helps you folks.
Good Luck,
Tony