It is well known that some local search algorithms for K-clustering problems could stop at a solution with fewer clusters than the desired K. Such solutions are called degenerate. In this paper, we first show that the K-Harmonic Means heuristic has this property, although it does not have the same initialization sensitivity as the K-Means heuristic (for solving the Minimum sum-of-squares clustering problem). We then found that two types of degenerate solutions can be found in the K-Harmonic Means heuristic and provide counter-examples of both. We also propose a simple method to remove degeneracy during the execution of the K-Harmonic Means algorithm (KHM) and use it within a recent variable neighborhood search (VNS) based heuristic. Extensive computational analysis, performed on the usual test instances from the literature, shows significant improvement obtained with our simple degeneracy correcting method, used within both KHM and VNS.