I think en: and commons prove you can't maintain a tree in wiki format.
Well, enwiki is by *far* the worst. When I analysed category structures of wikipedias, I usually found an average depth ovf about 10 and a couple of cycles with a circumference of about 20. enwp has hundreds of cycles, many of which are huge. The largest one i found has over 300 entries. That's insane.
So, basically: the fact that enwiki got it wrong proves nothing. Most other 'pedias do way better.
But categories as we have them are far from perfect, and it would of course be nice to be able to do "deep intersection" of categories. But "simple" tags would have two big disadvantages: ambiguity, and lack of a navigational structure. If we can get intersection, but retain the ability to categorize categories, that would be great. However, this means we need "deep intersection", which is something relational databases are notoriously bad at. I don't know how or if this can be implemented efficiently.
-- daniel