You searched the drive for *.pst and did not find it? How about searching the disk for filename.* (not pst). Although it should still be filename.pst it might have been changed to a temporary file somehow.
If you know the path of where the pst file was, you might be able to recover the deleted file with a "undelete" utility program (you can find these at www.download.com and download one to a floppy and run it from the floppy to search the c:\path\ for deleted files). You may be able to recover it that way if nothing else has since overwritten any part of the sectors on the hard disk drive that the pst file used to occupy.
Good luck.