Where does song files restored from recycle bin go?

Just a stab, but if you deleted from library AND computer, check to see if restored files exist in the iTunes Music folder in the expected spot. If the files are there, go to Files > Add files (or folders) to library and navigate to the files to add them back to your library. I hope it's that simple for you...;)

The Restore function in Windows puts the file back to where it was before it was deleted. If you want to know where that will be before you restore it, look in the Recycle Bin at the column "Original Location." (If the "Original Location" is not visible, go to View > Choose Details and check its box).

If you don't want that, you can just drag the icon from the Recycle Bin to wherever you want it, instead of using Restore.

Also note that putting a file back into the iTunes folder does not automatically re-add it to your iTunes library. You need to use the iTunes command File > Add File (or Folder) to Library.