If you would have checked the little box in the same window that told you the songs were not being removed from the player, it would have actually removed them. This allows you to remove songs from a certain playlist, but not the whole player (as in when a song appears in several playlists at once - you don't need multiple copies of the song).

To remove any "orphaned" songs that are on your player but not appearing in a playlist, do an Advanced Search for "refs=0" (remove quotes). This will show all of them. Just do a Control-A or select all of them and delete. This will free up hard drive space.