I would say dict's failure to call overloaded __setitem__ from 
setdefault is a dict implementation problem which should be either 
fixed, or clearly documented as warning to anyone who wants to derive 
from dict.

A fix would be trivial:

===================================================================
--- Objects/dictobject.c        (revision 61014)
+++ Objects/dictobject.c        (working copy)
@@ -1861,7 +1861,7 @@
        val = ep->me_value;
        if (val == NULL) {
                val = failobj;
-               if (PyDict_SetItem((PyObject*)mp, key, failobj))
+               if (PyObject_SetItem(mp, key, failobj))
                        val = NULL;
        }
        Py_XINCREF(val);

but I have no clue what performance or other implications would be.

Maybe something like this could be considered for Py3k - reviewing dict 
implementation to make it usable as DictMixin.  I'll write a complete 
patch if there is positive reaction.