Thanks for the updated patch.  Some comments:

- In the tests, your functions should have return type PyObject* rather than void;  you can use Py_RETURN_NONE as a convenient way to return something of the correct type.  E.g.:

static PyObject *
test_decref_doesnt_leak(PyObject* self)
{
    Py_DECREF(PyLong_FromLong(0));
    Py_RETURN_NONE;
}

- Unfortunately, the test above *will* leak:  even though your patch fixes Py_XDECREF, Py_DECREF will still evaluate the argument multiple times.  So we get, for example:

iwasawa:cpython mdickinson$ ./python.exe -m test -R:: test_capi
[1/1] test_capi
beginning 9 repetitions
123456789
.........
test_capi leaked [1, 1, 1, 1] references, sum=4
1 test failed:
    test_capi

- It would be great to have tests for Py_INCREF and Py_XINCREF, too.

- The patch introduces two extra blank lines before Py_CLEAR.

- Not specifically about the patch, but: there's a comment in object.h that reads:

"""
*** WARNING*** The Py_DECREF macro must have a side-effect-free argument
since it may evaluate its argument multiple times.  (The alternative
would be to mace it a proper function or assign it to a global temporary
variable first, both of which are slower; and in a multi-threaded
environment the global variable trick is not safe.)
"""

I don't understand why the author of that comment ruled out the possibility of a local temporary variable.  Anyone have any ideas?  A constraint of some flavours of pre-ANSI C, perhaps?