Hm I have to think about the best way to implement that with #autoedit. With inline editing within the tree you mean creating categories there "on the fly"?
What about the original request "autocomplete on Subcategories."?

A possibly bigger issue is that category trees themselves are, in my opinion, not an ideal data structure. [...] if page A gets added to category B, it's only for purposes of tagging and querying

I would concur that category trees that are created solely for input trees in forms are not ideal. But in my wiki, that's not the case. I have set up a wiki for a laboratory and people can use a form to create pages about lab devices (the Device-pages are added to a "Devices"-Category). To get a certain categorization of the devices, the users has the possibility to input a subcategory for the device-page he is creating (for example "Power supply", "Oscilloscope"...). That's why I use a combobox with autocompletion to let the user know about already existing subcategories. Of course, those Category-pages will also be used by the users to see what devices are available (of a certain type).

Missed the tree-input so far, thanks for pointing it out! Essentially, tree is great for choosing out of already existing subcategories. The problem is, that I would like to give the user the ability to type in a new category name. That's why I use combobox so far. I now thought about a combination of "show on select" (to display a textbox for input of the new name) and tree but then two new problems arise: 1. show on select is not supported by tree. 2. I would have to add an entry in the tree with something like "create new". That would have to be a subcategory itself (not very elegant) because manually adding something to the tree is not possible (probably with good reason).