The ViewModelLocator class helps keep a centralized store for your viewmodels. You can use this class to help manage new versions and clean up old ones. I always reference my viewmodel from view via the locator, so I always have code I can run to manage these things. You could try that.
As well, I use the Cleanup method to call Messenger.Unregister(this), which cleans up all references from the messenger for that object. You have to call .Cleanup() every time, but such is life 🙂