Not to be combative, but shouldn't you be asking Google to fix their broken IMAP?
I'm not sure, as I don't know IMAP very well. Is there a way that Google can send information about labels via the IMAP protocol without creating a duplicate message for each label? I guess they could add an email header with the labels, but that would modify the actual email.
The reason Gmail's IMAP is built the way it is is not because it maps well the semantics of Gmail to IMAP, but because it provided a reasonable way to access the semantics of Gmail using the semantics of Outlook. IMAP supports labels on messages in the form of user-defined flags; Gmail is really a single massive mailbox (what Outlook represents as a folder) with tons of flags. Most IMAP clients, however, suck at indexing flags, barely even let the user see and edit flags, sometimes only supporting five flags... it would have been useless.
I would really like something like IMAP, but have it embrace gmail style "labels" instead of folders. When you use IMAP with Gmail, each label creates a duplicate of the message in its appropriate IMAP folder.
Right now I'm aware of sup and notmuch, but they are mailstores and indexes more than transport protocols.