Deleting the files and emptying the recycle bin marks the areas that were used as FREE in the TOC (Table of contents) or index to the disk. The actual files are still on the disk until something overwrites them - You downloaded a file to try and get them back but where did it go? By the sound of it into areas that were marked as FREE in the disk index! End of story and files.

Cheers, TommysKeeper