Is there any reason for why IMAP keywords cannot be used for labels by e.g. having some prefix for the keyword which indicates that it should be interpreted as a label? Client support is of course needed but to me it seems like the IMAP protocol already supports labels. Maybe IMAP lacks the ability to enumerate all labels?
Gmail already has a bad hack for this: It reports labels as folders and that duplicate copies of emails are in them.
So the issue is that any other solution would work improperly for Gmail. Client support is a huge part of the problem: If it's outside the standard, clients aren't going to handle it the same way.
