Right, the UID is only unique per folder. The full persistent unique ID of a message is a tuple of the folder name, the folders UIDVALIDITY, and the messages UID. That tuple, on a correctly implemented server, will only ever refer to one message.
For example: (SENT, 1, 100) Indicates message with ID 100 from the 1st incarnation of the sent folder. UIDVALIDITYs tend to be about 10 digit numbers, and are supposed to change if the folder is deleted and recreated or needs to be reindexed/regenerated by the server software.