Inheritance is indeed overused and proxying is often a good way to work around it. The downside to that is that it eats up more memory, and runs slower.
While that is usually not bigger and slower enough to be truly detering, in some cases (mostly when you have potentially *lots* of object, for instance in a DOM tree) though it's clearly counter-indicated. I've been planning for a while to look into the ex::interface module on CPAN which is supposed to allow for interface inheritance but I haven't found the time at moments when my brain is in a good enough state :-/
PS: do you still have the code that made DESTROY not turn up in AUTOLOAD ? It should really be called explicitly... a code construct that doesn't force one to check for that would be interesting.