Fundamentally, the problem is that the IMAP standard does not support the concept of tagging, just folders. And GMail supports tagging but not folders.

GMail does a pretty good job of mapping tags to folders, but it ends up leaving edge cases that are hard to handle. Like how all emails will still be in the All Mail folder, even after you "move" them to another folder (tag).

I'm not sure there is any real solution, other than making mail via IMAP read-only.