Original discussion in http://drupal.org/node/1093338#comment-6906178. As I understand the current automatic deletion of messages only works in you have an entity reference field for the messages. I would like to see the cleanup working also for cases where a token reference fails.
E.g. a message that is referencing a user with a token [message:user:name] would automatically get deleted if the user in question is deleted.