UI idea
Here is an UI idea, which would require a close cooperation with mh's taxonomy browser. It's build on top of two parts, 1. a quick and easy UI for the creation of new terms while assigning and 2. the more extensive UI with all required flexibility and overview.
1. community categorization of nodes
People have an autocomplete tagging field on node view - with which they can tag the node. If the tag is new, it needs to be categorized. So you would need JS, that detects the new tag and asks the user for the categorization (small js taxonomy browser which shows only term categories (no leaves)?). It would be neat if it's possible to create new category (votes) for the term there too.
It would be cool, if voted categories also appear there, perhaps in another color.
2. community taxonomy manager
But what's completely missing, is a place where users get some kind of overview about the whole taxonomy. Which votes have been already placed? How can they vote for things like renaming terms, or recategorisation? So I would put a link to the "community taxonomy browser" on node view.
So, from the users point of view, I think it would be great if matthias' taxonomy browser, could work in "community" mode - where actions may require voting. Also important, it should show all voted terms again in another color, clicked on that term, user can vote for it, or also for placing it in another category, It should be also possible to see the votes of other people for that term, wherever they wanted to place it.
So what here would be needed, is a flexible taxonomy manager. You would need some hooks too extend it (display all votes for a term) and to separate the clicked actions from the logic behind (only vote instead of apply) - and so a good cooperation of you both would be needed.
I think this would get the user a really user friendly community managed taxonomy. While it's possible to do some quick things, mainly the creation and categorization of a new term, also with 1.
Voting tresholds
If you have a hierarchical taxonomy, it might be quite common that users vote for the same category. But it might be rare that user want to insert the same term - so multiple votes for the same term might be too rare.
-> Perhaps it would be a good idea, if it's possible to have the voting treshold apply for only X hierarchies. E.g. if the admin specifies a depth of 2, the management of the upper 2 hierarchies would be based on votings with the configured treshold, while the bottom is customizable directly (without votes).
So one can configure voting for more important categories, while the "leave tags" are creatable/changeable immediately.

Comments
Good ideas!
>characters as hierarchy separators, so you can choose (or create) your hierarchy from one field.Your proposal reminds me that on the first level I would still want it to autocomplete on all terms, so existing terms can be found, and that yes, a javascript expansion of the form to recommend further categorization of new terms not given a hierarchy as above would be ideal.
The hooks you describe could be responded to by the module that owns the vocabulary (the string in vocabulary->module), or taxonomy manager by default. This might be useful also for forum module, which may want to constrain certain reorganizations. In community-managed taxonomy's case, it would need to add suggested terms to those that actually exist, at each level, and the addition of a button to "vote for term at this location" in addition to merge and move.
Given the potential range, and the number of entry-points needed for just CMT, maybe the most sane way to do this would be to allow modules that own a vocabulary to take over the user interface entirely for their vocabularies, and try to use taxonomy_manager functions on the backend when possible.
Vaguely I'd had some thoughts along the same lines myself. I even toyed with the idea of putting uncategorized new terms automatically in a miscellaneous category.
One of the very neat things about the Drupal way of doing things, including taxonomy terms, is that treating every term equally allows for progressive enhancement. A huge list of terms may not be as useful as a categorized structure, but all of their links will continue to work even for the ones put twelve levels down or the ones that became super-categories themselves: to Drupal, each one is just a node.
One and three together, the goal is to let people create terms easily, and encourage them to categorize them.
benjamin, Agaric Design Collective
benjamin, agaric