Success!!!
I inherited my mothers iPhone 3Gs (as I was still using a 3G, as I am waiting to see what the iPhone 5 is going to offer) with the 3.1.3 iOS still installed (Thank GOD, as iOS 4 on the 3G is unbearable and it frequently crashes.)
After setting up the phone with all my settings, I kept getting the message that 2 email messages could not be sent and have been moved to my Outbox. No Outbox to be found. I wiped out all the email accounts and recreated them => I still received the 2 unsent messages and the phone kept trying to send them every time I accessed the email accounts from the iPhone.
I wiped out all the accounts again and then shut down the phone (pressed and held the main iPhone control button while pressing the power button and shut the phone down. Restarted the phone and setup my email accounts again => Success! No more unsent messages!