The problem is that IMAP is a crappy protocol. How do you layer tags onto a protocol where that was never envisioned? Where a basic function "move between folders" is an extension and not in the original protocol? IMAP doesn't even guarantee that message IDs are consistent between mailbox listings! (there's a great rant about how terrible both IMAP and all the IMAP servers out there are, can't remember by whom)

I'm just glad Google still support IMAP at all instead of going fully proprietary protocol like they have with calendars, where they gave up on iCal.