(Side note: It's been a few years since I looked through the specs and maybe I missed something)
IMAP flags are sadly severely lacking in what they can represent. The character set isn't even enough for unmodified UTF-7 (Punycode could work, but only for one-word tags) which renders them useless for user-chosen labels so few mail clients actually bother supporting them in that way. Thunderbird uses \label1 through \label5 but the names that are displayed in the UI are stored on each computer separately so you'd have to set up the labels you use on each machine (which kinda defies the purpose of storing that on the server). And short of using a »label configuration mail« on the server I don't see an easy way of supporting them completely server-side.
I'd love to completely forego folders and use tags/labels/flags/whatever they're called exclusively but last I looked IMAP wasn't able to support that.
You can determine labels, it's just more work. I wrote a script a while back that used IMAP to just generate a list of message-ids and the labels associated with each one. I iterated over all messages in all folders to build the associations. It might be possible to query for a single message-id in all folders, to get a list of labels to, but you would need to know the message-id ahead of time.
