A lot depends on what you are trying to achieve. In my case, for example, I wanted to group images that may have perceptually similar colours either as a dominant component or as an accent (say, a red shirt and a white shirt with red stitching).

To expand on your points, based on my own experience:

* Rather than using the centroid to represent the cluster, pick a representative peak from the hue histogram. This tends to make things less muddy.

* Not only do I throw away extreme S/L values, I aggressively weigh everything by S * (0.5 - |0.5 - L|), so bright, saturated colours dominate. Black and white are usually very thin slivers, and I almost never have grey.

* As a last step, I convert to Lab space and merge any colours that are perceptually similar (dE < 5.0). This means that large gradients (like an unevenly lit surface) only occupy one sliver of the pie. Unfortunately, in my current implementation this conflicts with my first point above, so the colours I end up with aren't always in the original image -- something I need to fix.

Here's my result for one of your images: https://dl.dropbox.com/s/azl2bag84riugg8/imghist.png, notice how the orange has a disproportionally large weight because it is so saturated.