One trick I used when facing this problem was to download and install Mozilla Thunderbird and set it up to check the same account via IMAP. This requires that you move all the messages to the server via IMAP, which can take some time (27,000 messages in my case). Then you can install a plug-in into Thunderbird that automatically locates and eliminates duplicates.
Once everything is cleaned up you can use whatever IMAP capable program you want to manage your mail. Just make sure you use the option to sync messages between the server and client so you can access your mail offline.