Based on this plot, my naive reaction would be to decide that DBSCAN is the best algorithm, as it recovers the (qualitatively) best clusters in each case. Anybody has experience with DBSCAN? What are the downside?