Have you tried deleting everything in the outbox, restarting Outlook, and trying to send again?
Often times we have seen issues with messages getting stuck in the outbox. There are usually two remedies: restart Outlook and hit send/receive, or getting rid of all the messages in the outbox and then restarting.
Also if you don't want to delete the messages I suggest moving all outbox items to the drafts folder, then restart Outlook, and then resend each message from drafts. These methods have worked 100% of the time for us.
Are you connecting to Exchange or a POP account? Have you checked the server configs (or talked to your admin)?