Let me rephrase my example with real paths.

Python creates /usr/lib/python3.3/site-packages.  (I’ll call this $stdlib.)

pysetup3.3 install paste.script creates $stdlib/paste/script/ and files therein.  The paste and paste/script directories are recorded.

pysetup3.3 install PasteUtil creates $stdlib/paste/util/ and files therein.  Only the paste/script directory is recorded.

pysetup3.3 remove PasteScript deletes the $stdlib/paste/script dir, but not its parent, as it’s not empty after removing all files and dirs in PasteScript’s RECORD.

pysetup3.3 remove PasteUtil deletes the $stdlib/paste/util dir.

The $stdlib/paste directory is created by either distribution when it is installed, but if it’s recorded only by one of the distributions, then it can’t be removed when the other distribution is removed last.  This is the problem I’m seeing.