Lost mail from Outbox in Mail 7.1 (1827)
I, too, lost my Outbox, but for a different reason.  

I composed 15 messages on an airplane and "sent" them, which put them in the 'Outbox'.  When I arrived home, I:


Cmd-A (to select all 15 messages from Outbox) 
tried to send them (via Cmd-Shift-D)
answered 'Yes' to "Send all these messages?"
noticed that they were gone.  G-O-N-E.  Nowhere to be found.


I eventually found them in:
  ~/Library/Mail/V2/Mailboxes/Outbox.mbox/some-UUID-here/Data

By selecting a time that was an hour (or so) before their disappearance, I was able to restore them from my online backup service to a different location (e.g. ~/Desktop/mail_app_message_restore).  I'm betting that TimeMachine could do something similar.

The messages were distributed (hashed, actually) among many directories, but when I issued this command from the command line, I found all 15 missing messages:

$ cd ~/Desktop/mail_app_message_restore    # or where you restored them
$ find Outbox.mbox -type f
Outbox.mbox/14D01FAB-9E5D-420D-8507-240D11CEC6D4/Data/5/4/1/Messages/145098.emlx
[ 14 other files ... ]
$


Notice that the hash directories (e.g. Data/5/4/1) are just the reverse of the top few digits of the message filename.  All of mine were in this 5/4/1 directory, but your numbers will be different.  It's a big directory structure, but there were only a few messages sprinkled through it.

Best of luck!!!
Michael

P.S.  Notice the side benefits of automagic backups?  What a great feature!  I'm so glad that it got a snapshot as soon as I got online, but that there was time before I tried to send them.  I think TimeMachine would have been even better about taking offline backups before I reconnected to the network.