Ok, this issue was really insane. Thank you very much Antoine Pitrou for explaning me the root bug ("int - int") and for the fix. The bug is now fixed in Python 3.6 and master (3.7). I checked manually the applied fix on the Gentoo Refleak 3.x buildbot using test_code and test_sys run in a loop: no failure after 30 runs.
*Hopefully*, it was a bug in the test, not in the code ;-)
The fix should help to detect real memory leaks, and maybe we can now replace again all() with any() in libregrtest/refleak.py to detect more leaks: see bpo-30776.