Well maybe this is a feature, but a very very bad one.
when you remove an entry from library, the file is deleted from all playlists. This behavior is wrong and dangerous. Playlist sequence is important, sometimes more important than the files themselves as I have discussed in the past. The correct behavior would be that the playlists show an entry for the removed item, marked in a special way (e.g. similar to entries in the playlist with missing physical files).
I also want to point out that unlike tags and files that can be backed up externally and synchronized back, There is no good mechanism for restoring playlists (when you import external playlists, you loose the directory structure). This makes the problem even more serious.
Technical details:
I am guessing that MC does not store file details on the playlists therefore it cannot show removed entries on the playlists. I think MC should maintain an internal database for all files removed from MC but stay on some of the playlists. The entries in this internal database should only be removed after they are cleared from all playlists.