What type of files were these ? ?
Do you know how or in what manner they were deleted ? ?
Have you tried to locate them using Windows Search ? ?
You don't neccessarily need the entire filename for this to work but it would be helpful.
Are there multiple user accounts setup on this machine or just one ? ?
Please answer all the above as much as you can as there may be different recovery options...
p.s. The HDD space isn't going to show a noticable change with only 2 files...unless they were both 5 hour movies