I'm ever the optimist. In the event that the user was deleted and not just the messages only then it may be possible to recover them. Not likely but maybe.
Install testdisk and run it as admin. Run the first option on each page until you get the partition listed where your user home is. P lists the files and you would navigate to drive:\Documents and Settings\<user>\Local Settings\Application Data\Microsoft\Outlook and look for a pst file in red. If it is there copy it somewhere else on the drive where you can find it and the go to outlook help to find instructions on importing a pst file.