A quick way to zap the songs deleted in any playlist is to use the "refs=0" advanced search, and delete the songs that show up there.

Thats what I have been doing, since the workaround of not having the "delete files with playlist" seems to be working.