I don't know how tags or flags would be attached to emails, (other than as a local and private action within Thunderbird), so for this to work reliably, I think the server must support tagging, and Thunderbird must be capable of working with the server's tagging mechanism. I don't know of any provision for this in the email protocols, other than urgency levels.

Tags in Thunderbird can be quite arbitrary and may be defined by the user, so even if tags were transferable, there's absolutely no guarantee that a tag set up by one user would mean anything to another user.

I'm surprised it works at all.

Hmm, I thought this flag mechanism is some kind of universal function, as I have seen flagging to work across several email providers, and several email clients. My email provider said I should look an answer from Thunderbird itself, not from server or client-to-server communication standpoint..

To be sure we are talking about the same subject, with flag I mean the "star" icon next the message subject..

IMAP also supports message tags, but the implementation is server specific. Some mail server products support it, other do not. It is a bit of a lottery when you first try and if the provider changes software providers then your back to the lottery.

This is also so with the values that can be flagged. the numbers 0-9 appear to be almost universally stored. Once you move on from that is becomes again a lottery.

You can connect to the server using telnet and query the server directly for the information about what is managed and what values it supports. But it is a fairly advanced topic. Better in most cases to just try it and see.

A quote from RFC3501

 A keyword is defined by the server implementation.  Keywords do not
  begin with "\".  Servers MAY permit the client to define new keywords
  in the mailbox (see the description of the PERMANENTFLAGS response
  code for more information).

This information for better or worse is stored in the MSF file. generally it's considered an index into the real mail in the mail store. Developers however call it the database as it actually contains the flag data. Beyond Flags I do not know what the file actually contains, but it is the reason the repair folder option was created, because the file holds more than just an index.

For clarity. It is Thunderbird tags that synchronize, not labels. Likewise the star is defined in imap and is, as far as I know, universally supported.