How do you create a new IMAPMessage?

Let the Store create it for you.

No, really. Create your new MimeMessage. Call Folder.appendMessages() on the target folder. Listen for the resulting MessageCountEvent telling you that the message has been added. Use MessageCountEvent.getMessages() to get the newly added message. This message will be a proper IMAPMessage, and you should be able to use UIDFolder.getUID() on it.