GMail freed us from the tyranny of trying to build a single ontology for organizing email. To me it's the most radical and admirable thing Google has done by some measure. I would very much like to see this approach applied to other areas of HCI. The fewer flawed assumptions baked into semantics, te better.

Tagging also existed in Opera's email client as virtual folders, back when it was known as M2.

And zimbra

This is a great feature but is older than GMail. Lotus Notes mail for instance allowed the same mail to appear in different views, including an "all documents" view that had, as you might expect, everything in it. This advance was rather let down by the rest of the Notes client interface however: http://hallofshame.gp.co.at/lotus.htm

Wow, blast from the past. My first serious use of email was Lotus Notes. It had some really cool features but also really strange ones, such as using the escape key to send a message.