To remove songs from the Playlist you use the Remove button not the Delete button. Once they've been deleted they're gone. Playlists are only references to the files in the library. (It's like clicking on a link to a web page, it's just a reference it's not the actual web page.)

What I'd suggest you do is use a file recovery tool to try to recover the files from the HDD. Try http://www.gnutellaforums.com/showth...threadid=34134 & about half-way down the page I have a link to some free file recovery tools. 'PC Inspector File Recovery' sounds ok. Though it may crash it does the job & is free. Read the reviews.