Metadata instances do NOT get removed automatically at all! Take an Entity for example, If the entity has a metadata of 123, and that same entity dies, the metadata stays in the EntityMetadataStore.

I've never really liked the way the metadata is currently stored. I think they should be stored in the Entity instance instead, that way it can easily get gc'd or manually cleared (on death). I believe this is the way to go to make everyone's life easier, and of course fix any leaks from already existing plugins. I know I don't want to have to track every entity I add some metadata to, and have to listen to it dying.