This is a pop account? If it's imap, check the sent folder on the server, if they are there, the folder in outlook needs resynced or the view reset.
Do you have more than one data file in your profile?
What Addins do you use? Look in file, options, addins.
Are you browsing to look for the messages or using instant search? If browsing, reset the view.