This is quite amazing. The quality of the created palettes is surprisingly good.

For the fourth iteration (guarding against phantom blue from shadow pixels), I wonder if it may help to also take into account how close the pixels in each cluster actually cluster together in the actual photo. (None of the heuristics used here seem to be interested in the position of the pixels at all, only in their values - as-is, it seems one could sort the photo's pixels before running the program and get the same result.) Actual objects usually form connected areas, whereas at least in the fruit image, the phantom shadows are spread across the entire photo in largely disconnected chunks.