Message-ID is not unique per message, or per folder or user. The trivial counterexample is a message that goes through a mailing list may exist from the list and in a Sent folder with the same Message-ID but possibly different content, among other (less convincing) reasons.
A UIDVALIDITY change should blow your whole cache. In practice they are rare.