What's a decent IMAP client that supports labels properly?
I use notmuch[1] with lieer[2]. Notmuch maintains a tags database with full-text search indexing for a set of maildirs, and Lieer uses the GMail API to synchronize messages with a maildir and labels with notmuch tags. There are lots of notmuch frontends available, but I use the built-in Emacs frontend.
Geary[1] is one option for Linux users. It stores all messages in a giant sqlite database and models labels by "tags". It's still defintely wip though.
I do recall reading somewhere that these days Thunderbird does deduplicate messages with multiple labels, but I haven't tested whether it is indeed true.