I've done some work on this patch, including porting it to HEAD, streamlining some aspects for comprehensibility, and verifying correctness.  My performance results are a little less dramatic, ranging from 10% speed up for simple non-heavy OO code to about 25% for applications with deeper object hierarchies.  Given the very attractive speed up, I'm happy to continue along this patch, but have a few questions for both Raymond and Armin:

1. Am I duplicating effort?

2. Should this optimization be targeted only toward the Py3k branch, as some of the trickier logic goes away (no old style classes to complicate things).

3. Should this patch be targeted to Python 2.6 as well?

4. Armin, can you explain why a type_modified call is needed in the __module__ setter?  I don't immediately see how this affects the mro.

5. A minor nit: I'm not thrilled that the has version tag is cleared when the type has an unsupported base class/mro.  I realize why this is convenient, but it bothers me because __bases__ is mutable and the flag cannot be reset once unset.  I realize this is possibly a vanishingly rare case (__bases__ is not likely to be reset often) and that correctness is not at stake.  Regardless, I'd be interested in exploring strategies that do not add more flags or complexity, but also allow for types to recover their valid version status after unsupported bases in the mro are removed.