I have GMail synced via IMAP using offlineimap on Machine A and Machine B. I accidentally deleted 5000 messages when trying to sync Machine B. Machine A was off at the time, and so I still have those messages. The problem is that Machine A and Machine B give the emails different filenames in their Maildirs.
A more abstract description of the problem is that I want to merge two directory trees, by considering only the contents of the files, and ignoring the filenames.
Unfortunately I'm not sure that there is anything in the filenames that can reliably identify its match in the other directory tree.
(one possible route that I will try is to simply re-sync Machine A and then restore the emails from its own backup. Then I won't have the filename problem! But now I find this question interesting so I will post it anyway)