Go into the "soup views" (artists, albums, whatever) and find the tracks there. Those are the "real" tracks. The ones in the Playlists tree are just pointers to your tracks.

In recent emplode versions, I think it gives you the option to "really delete" the files when you delete them from the playlist view, also.