I don't know what you mean when you say UIDs are not unique in a mailbox, just in subfolders. By subfolders, do you mean anything other than INBOX? In any case, it sounds wrong. UIDs are in fact unique within each folder and it doesn't matter it it's INBOX or any other folder.
What can happen is that UIDs can change between sessions. Generally this happens if the IMAP server loses its indexes and has to rebuild them or if the mail is migrated from one IMAP server to another, etc... If this happens then you will of course lose all of the associations between emails and extra data (notes or contacts).
You can rely on this: a UID will never suddenly refer to a different message. Either it will remain valid and refer to the same message it always referred to, or else it will become invalid.
You might want to check out how your particular IMAP server generates and maintains UIDs. Different IMAP servers make different promises about the persistency of UID values. Even within one IMAP server, it may vary depending on which mailbox format is in use. For example, with Dovecot, expect less fragile UIDs with mdbox than with mbox or Maildir because the metadata are more tightly integrated with the actual emails with mdbox.
I suggest using UIDs to refer to messages on the IMAP server, with
Message-ID as a backup.
Message-ID is not as good because duplicates are possible and (for most IMAP servers) searching by
Message-ID might be slower, but it's better than losing track of the messages completely.