Firstly a caveat. In clustering there is often no one "correct answer" - one clustering may be better than another by one metric, and the reverse may be true using another metric. And in some situations two different clusterings could be equally probable under the same metric.
Having said that, you might want to have a look at Dirichlet Processes. Also see this tutorial.
If you begin with a Gaussian Mixture model, you have the same problem as with k-means - that you have to choose the number of clusters. You could use model evidence, but it won't be robust in this case. So the trick is to use a Dirichlet Process prior over the mixture components, which then allows you to have a potentially infinite number of mixture components, but the model will (usually) automatically find the "correct" number of components (under the assumptions of the model).
Note that you still have to specify the concentration parameter $\alpha$ of the Dirichlet Process prior. For small values of $\alpha$, samples from a DP are likely to be composed of a small number of atomic measures with large weights. For large values, most samples are likely to be distinct (concentrated). You can use a hyper-prior on the concentration parameter and then infer its value from the data, and this hyper-prior can be suitably vague as to allow many different possible values. Given enough data, however, the concentration parameter will cease to be so important, and this hyper-prior could be dropped.