When you delete a song from a playlist in iTunes, the song not actually deleted from your iTunes library. The song is removed from the playlist, but is preserved in the iTunes library. iTunes was designed this way – otherwise, it would be far too easy to permanently delete music from your iTunes library by accident.
However, I’ve found that it is possible to permanently delete a song from your iTunes library even when the song is in a playlist. Simply highlight the songs you wish to delete, then hold down the option key while you press delete (on most keyboards the option key can be found to the left of the Apple / Command key.)
When you do this, a dialog box will pop up asking “Are you sure you want to remove the selected songs from your iTunes library?” If you click “remove,” the songs will be deleted from the playlist AND your iTunes library. The songs will be placed into the trash.
This is especially useful if you use Smart Playlists. For example, if you want to permanently delete all the Milli Vanilli songs in your iTunes library, you could create a Milli Vanilli Smart Playlist, then use option-delete to permanently delete all of their songs.
You can learn all about Smart Playlists, including what they are used for and how to make them by clicking here.