everything you see in iTunes is basically a shortcut. It just points to the file in the library. If the files were deleted, they become useless.
The fact that you still can play some means that not everything was in the iTunes folder, but whatever was is probably gone unless you can use a file recovery program like stated above.
When stuff is deleted, all information about the file is deleted, not the file itself. It basically becomes Invisible to the system. It lies in the free space on the hard drive, and will remain there until you write something to the drive (it gets written over), which happens a lot either by you making a new file, copying files, or a program writing temporary files to do it's work.
I'm not sure how file recovery works, if it will find "file001" and you have to guess what the name was one by one, and even guess what the extention was "mp3" "txt" etc.. if that is the case, I wouldn't think it is worth the trouble
Or if it can somehow recover the info that it had prior to being deleted. You should always make backups of your music for this reason. I just burnt 6 single layer 4.5GB DVDs to backup my library. I also have a copy on my External HDD.
the best way to backup is:
-go into the actual "iTunes Music" folder
HDD/users/yourname/music/iTunes/
-burn the folders to disk (copy the artist folders A-F to one disc..etc..) you'll have to make it work, as the discs have limited size. What I did was select artists A-F in iTunes, drag it to a playlist, and looked at the size. If it was around 3GB, I would use that for disc 1. do NOT burn from iTunes. (well you can, but that is not what I'm going for here)
-Once all artist folders have been backed up, burn the contents of the "iTunes" directory, excluding the music folder you just burned. You can also exclude previous libraries folder. Just make sure the rest is saved, such as:
-album artwork folder
-iTunes library file
-itunes library xml file
-everything else that is there
When you restore them, just copy all the music folders back where they were, and copy the library files back replacing any that may already exist. iTunes will open, and read the saved library file, and you'll have everything already set. Artwork, songs, everything. No re-sorting, re-adding, re-downloading artwork.
