If they're not still in your deleted items folder, try checking your preferences or options for the mail account and see if messages are left on the server or deleted.
If you havent ticked the delete from server box then they'll still be on the server and should be retrievable - you would need to go in using a web browser (web mail) to see them. Contact your ISP if this is the case (or it may be in the documentation you got when you signed up).
To avoid this sort of situation, it's a good idea to take a back-up regularly, depending on how many emails you send and receive. Search your hard disc for the file outlook.pst and save it to a CD, floppy disc or another location on your hard disc.
If you need to restore the file, don't forget to save the current outlook.pst file or you'll lose everything you've sent or received since the file you're restoring!