Perhaps this is a better question for the PEP rather than the impl, but can attributes be abstract?

class Foo:
  abstract_override_me = ???

If so, then __isabstractmethod__ might be better named as:  __isabstract__.  I think this might work:

class Abstract:
  __isabstractmethod__ = True

class Foo:
  abstract_override_me = Abstract()

Do you want arbitrary objects to be able to declare their abstractness or should the impl also check that an attribute is callable?

check_new_abstracts() should return a Py_ssize_t since it returns the size of a container (set).  The return value is already captured in a Py_ssize_t, so it's just the signature (and prototype) that should change.

PySet_Add()s return value isn't checked in check_new_abstracts().  It might be nice to factor out the common code between the two new functions into a static helper function.  That would get rid of the PySet_Add problem.

By calling: PyObject_GetAttrString(meth, "__isabstractmethod__"), that means a new string object is allocated and then thrown away with each call.  This could be improved by creating an interned string for "__isabstractmethod__".  (I realize this is only when types are created which shouldn't be too often.)