Why wasn't message id enough to identify duplicates? It must be unique. All messages with identical message id are duplicates unless you haven't modified them locally.

Actually, old Eudora had an option to delete duplicates based on message-id that, if selected, was applied every time you opened a mailbox. A very simple and elegant solution.

I would be interested in finding a script for IMAP-mailboxes doing this. Anyone?

Assuming mbox format (such as used on some IMAP servers, or from the "Archive Mailbox" in Mail.app, save this as something like /usr/local/bin/mbox-removedup.sh
then run it on the mbox in a terminal:
sh /usr/local/bin/mbox-removedup.sh ~/Inbox

--begin copy--
#!/bin/sh
formail -D 10000000 idcache < "$1" -s > ztmp && mv ztmp "$1"
rm idcache
--end copy--

Care to explain how your script works?