Am I correct in assuming that you DO NOT have a backup of your data for such problems as this?
If that is the case you need to copy the .tmpxxx files (assuming they are the complete and readable) over to a computer where they can be renamed using a batch script. When you have them all renamed, checked for consistency and in the correct directories, turn off the recycle bin and delete the old directory and what you recovered on the NAS. Then copy the complete directory structure and files back to the NAS.
Finally, make a full backup of all the data on the NAS to another drive somewhere safe then start a daily backup of the changed data that you store on the NAS
Unfortunately I can't comment about how the recycle bin works because we never use it nor do we set it up for our clients (having a reliable, tested full backup is a much safer option) but I assume its main use is to catch the odd file that accidentely gets deleted rather than the vast number you have.