The UIDVALIDITY is actually a great design. IMAP servers will usually store the UID mapping in some kind of index that is used even across restarts. Therefore in normal operation this is not a problem. When did you encounter problems with this in every day use?
If the UIDs were not allowed to change, you would run into practical problems on edge cases. What if you switched your IMAP server implementation? What if the index files on server side got corrupt and you had to rebuild them? What if you had a fatal disk failure and had to restore an older backup? Mismatching UIDs would be even worse than a way to indicate to the client that the previously retrieved UIDs and associated messages are no longer valid. UIDVALIDITY is basically just a way for cache invalidation.
Where UID is used now sounds like a good use case for UUIDs (or GUIDs?) that don't ever change.
I don't specifically know the history of IMAP, particularly IMAP UID, but the semantics of UID to me implies that it was originally specified to permit its implementation as the file offsets into the mbox files that backed the store, and I believe some IMAP servers implemented it that way.
Some IMAP server implementations have a custom attribute they use to indicate a globally-unique message ID.
[1] The IMAP protocol used to rely heavily on message sequence numbers, where each message in the folder was numbered sequentially from 1-N, and deleting messages caused all subsequent messages to have their number decremented by one. But you can have multiple connections active on the same mailbox, and you can't always immediately notify the other connections of when things get deleted, so every connection can have a slightly different mapping. So everyone uses UIDs now, which are guaranteed to be unique, until the server feels like deleting them all and restarting from scratch (i.e., updating UIDVALIDITY), so every message has a different UID now.