Over the past few weeks, I've been working with Stefano Zacchiroli on a small patch to notmuch-mutt to remove duplicate search results. After several iterations, the patch was accepted and committed by upstream. It won't be in wheezy, but it feels good to have something committed and hopefully used by others in the future.
Currently it only removes actual bitwise duplicate results, but we've talked about adding removing duplicates by message-id too. Notmuch may be able to solve this problem for us, though, by adding a new search option.