Okay, so it looks like the weight cleaning operation only removes vertices from groups when it's done in object mode. In weight painting mode, the weight is set to zero, but the vertex remains in the group.

So, a potential workflow for me might looks something like this: parent the mesh to the armature with automatic weights, do a weight clean-up in object mode to reduce the influence zone of each bone to something more sensible (using 0.2 as the minimum preserved weight looks reasonable here), go through the bones and remove more areas of influence I'm sure the bone should not have, with an additional individual clean-up after doing each bone, then start fine-tuning the weights with "restrict" on. If I cut off too much of a bone's area of influence, I can always carefully add it back later with the "restrict" option temporarily off.

We'll see how it goes. I might still have to make further adjustments, but I'm glad I'm starting to get an idea of how to deal with some of this weird behaviour.

-- I'm not mad at you, just Westphalian.