I would like to point out that, at least in the case of Gmail, the UIDs of emails are changed if they are moved from one folder to another. Even if moved back to the same folder the UIDs get incremented and thus changed.
I found this the hard way after relaying on the notion that UIDs do not change as I found almost everywhere in the docs.