I have got the problem, all of a sudden, of Windows XP deleting files first time instead of putting them in the Recycle Bin, which I think I have got a solution for, but can Recuva recover the files that are stuck in the Recycle Bin (if they are still in Windows obviously?)
Right click on the recycle bin, chose properties, check "custom size" instead of "don't move files to the recycle bin"
As for the second part, you can try it, but I don't know if that'll work.
you can manually navigate to the C:\RECYCLER or C:\RECYCLE.BIN folders?
If files are in the recycle bin I would expect that you could open the bin and restore them to where they came from.
If files have been deleted and exist in "free space" I would not expect Windows to place them in the Recycle bin.
Do you think that Windows actually put your files into the Recycle bin and then Emptied the Recycle Bin ?
I do not think that can happen - but to be honest Windows never does what I think it should do.