Sounds to me like your email's have been archived. Outlook offers a feature to store your old emails directly on to your hard drive rather than your email client.
If you search your hard drive, you shouldn't be able to find them. Your archived emails are saved as a .pst file in your documents and settings folder.
You can find the file by opening your email client and selecting the "tools" menu, then the "other" tab, then the "auto archive" button. Around the middle of the page you should find a directory there. This is where your archived emails are.
Check the help section in Outlook to find out how to restore archived emails.
I hope this helps.