[vhbit]

As I remember IMAP allows to add freeform flags to every message.

[StavrosK]

IIRC that's how gmail implements its labels.

[pferde]

I don't think so, since gmail had labels before they added IMAP support. Also, when accessing gmail via IMAP, you see the labels as IMAP folders, which leads me to believe that they just bolted the IMAP interface on top of whatever backend they use to store messages internally.

[StavrosK]

I meant that that's how they implemented labels for their IMAP support, but you may be right, they may be folders instead.