I guess it is safe to assume that your OS Trash file does not hold the files and that you do not have the Mac Time Machine running. Although the result of the app you used was unsuccessful perhaps another recovery app may be more successful. This site may be useful:
One bit of advice: Act promptly. Adding and modifying files may overwrite what is now considered as usable disc space, further destroying the deleted files.
Thanks! I failed to mention... It's Windows 7 Pro. Not Mac OS. And, nope - not in Recycle Bin.
Where these PSD's stored on the C Drive and do you have system restore setup, if so you could try a system restore
Bit late now but you should always have a backup of your important files
Here's two articles from trusted sources (meaning they are not trying to sell you something):