They're gone forever! Sorry
Lexie's procedure only works if you've installed Outlook (as opposed to Outlook Express) with the Corporate Workgroup/Other option. To determine your installation type, on the Help menu, click About Microsoft Outlook. You will see "Corporate" in the About Microsoft Outlook dialog box if you have the Corporate Workgroup installation.
Emails aren't like Windows files, they're stored in a database (search for inbox.dbx on your PC if you want to find its location) so they cannot be restored.
R2's top tip No 1 - don't delete emails, leave them in the deleted box forever.
R2's top tip No 2 - upgrade to Outlook instead of Outlook Express, it comes with MS Office (2003 is the best version IMHO) and has lots of extra features such as calendar, to do lists etc etc
Backup your emails!R2