Isn't the Outbox the same as Sent? You've confirmed that emails you attempt to send don't get received by the addressee?
What email account are you using? You may want to double check the outgoing SMTP server settings in the Email app's account settings. Check with your email provider to find out the exact SMTP server settings.