I switched to Fastmail from Gmail years ago. In the beginning I missed the tagging when I went back to a folder structure, but you get used to it.
Other then that, I'm super happy and can only recommend the service.
A single table in a database mapping labelName to documentId can implement labels with no extra constraints, and it scales really well.
Put an index on labelName and you can easily list all documents with a given label. Put an index on documentId and you can easily list all labels a document has.
I don't understand why other providers go to the significant extra effort of trying to implement directories.
FastMail's choice to wait until a new standard that supports it is available is a strong choice towards interoperability and standards.
I wouldn't say labels are widely used, Gmail is still really the only provider doing them I know of. It's just that that one provider is a monopoly.