I didn't read most of this length thread the first time through, but I did run into the bug today in my own code and tried to fix it. I added a patch to 518846 that allows instances of new style classes, where the check is implemented by checking Py_TPFLAGS_HEAPTYPE, which is only defined for objects created by class statements (I think).
This doesn't seem to cause any change in the behavior of string-based exceptions. I don't think it's necessary to have "except str:" catch string-based exceptions, because they're supported solely for backwards compatibility.
There was also some discussion of making exceptions inherit from Exception, but I think that's a separate issue.
Any reason not to commit the patch?
In how many places have you posted about this issue? This is the third place where I see you trying to get people's attention. What's the urgency? :-) I don't think the patch is ready yet, see my comment on SF. If we decide that anything needs to be done in this area I want to look at it first, so please don't check anything in yet. --Guido van Rossum (home page: http://www.python.org/~guido/)