If they aren't in any other folder (including Deleted Items or as a
sub-folder of Deleted Items) then they are probably lost.
Do you synch a mobile device with Outlook? This problem can sometimes be the
result of a synch issue. If they happen to be on a mobile device you might
be able to recover them from there. Also look for any additional PST files
you might have - open them and see what's in them.