I only want to address a few of your points here where I think you actually are mistaken in your assumptions.

3. Method resolution gets very messy, very quickly.

Should the inheritance tree be search breadth-first, or depth-first, or depth-within-breadth, or breadth-within-depth, or depth-within-breadth-within-depth, etc.

... snipping a bunch of other stuff ....

You should take a look at the C3 method resolution order (see the SEE ALSO section of Class::C3 for some links). It preserves local precendence ordering of classes so that method lookup becomes much more consistent and predictable from any given point in the class hierarchy, as opposed to other (more common) method resolution orders which can change depending upon where you are looking at them from. In short, it makes MI method resolution order Just Work.

I think your (sort of) proposal for classes to control their own dispatching is a really bad idea for all the reasons you pointed out. IMO it would make it almost impossible for a programmer to understand the path his method resolution would take.

4. If any level of dynamism in the class hierarchy is allowed--introspection, never mind runtime modification--then the overheads are huge.

The cost of maintaining the data required for runtime introspection of a wide and deep MI tree are daunting enough.

... snipping a bunch of other stuff ....

You are making assumptions here about how the introspection mechanism is being implemented. IMO there is absolutely no need to maintain any seperate data for runtime introspection. Sure, that is how C++ and Java do it, but they were never meant to be "dynamic" languages, and any "dynamic" features they have are clobbered on (very poorly too, IMO of course).

You also mention vtables a lot in your discussions, but vtables is not the only way to implement objects/classes. In fact it is a very poor way to do it (again IMO). If you have a cached method resolution order (MRO), especially one like C3 provides, then method lookup is not nearly as painful as Perl 5's depth-first-left-to-right mess. And since your MRO will only change if your class heirarchy changes, then the cost of cache maintaince can be managed quite easily.

In fact the Perl6-MetaModel prototype I created did just this. The MRO would be cleared out and re-generated if and only you changed a class's superclass list, which meant that adding methods to class dynamically (a far more likely usage) would have no penalty. I also memoized the method lookup (since we have a predictable MRO and we can pretty much assume that method lookup is a side-effect free operation), which is really the only other place we needed to deal with cache issues (although I say that with some hesitation since I am sure there is something I am overlooking). This approach is IMO a far better approach that vtables.