It's possible that shift delete was doing the opposite of what you think it was doing.

To find files that aren't in playlists, do an advanced search for refs=0 .