How is SUPER implemented? I think it would make more sense to leverage that code and make it part of Perl itself.
I doubt there would be much code to leverage. Beyond the lexical similarity there's not a lot of common ground. SUPER is doing a runtime method lookup, while MY is doing compile-time namespace fiddling.
An alternative I prefer better is to make it an attribute
You could use an attribute to wrap a method to check it was only called on objects of a specific type. However this would still leave the method in the same name space, which leads to the original problem of subclasses breaking due to implementation changes in the base class.
You could also use the attribute, I guess, to mark methods for later transfer to another namespace in an INIT block - but that would still leave the method calls to be dealt with. You'd have to use a source filter for that - or use the full package name of the private namespace which CanBeTedious.
Of course in Perl 6 it would both trivial (since we have a decent macro system) and unnecessary (since Larry and friends are making what looks to be a very nice OO environment).