Is k-means++ meant to be perfect every time? What other initialization strategies can yield the best k-means?

I've implemented a k-means algorithm and performance is highly dependent on how centroids were initialized. I'm finding random uniform initialization to give a good k-means about 5% of the time, whereas with k-means++, it's closer to 50%. Why is the yield for good k-means so low? I should disclaim I've only used a handful of data sets and my good/bad rates are indicative of only those, not broadly.

Here's an example using k-means++ where the end result was not great. The Dunn Index of this clustering is 0.16.

And an example where it worked perfectly with a Dunn Index of 0.67.

I was maybe under the naive impression k-means++ produced a good k-means every time. Is there perhaps something wrong with my code?

def initialize_centroids(points, k):
    """
    Parameters:
        points : a list of Points.
        k : how many centroids to place.
    
    Returns:
        A list of centroids.
    """
    clusters = []
    clusters.append(choice(points)) # first centroid is random point
    for _ in range(k - 1): # for other centroids
        distances = []
        for p in points:
            d = inf
            for c in clusters: # find the minimal distance between p and c
                d = min(d, distance(p, c))
            distances.append(d)
        # find maximum distance index from minimal distances
        clusters.append(points[distances.index(max(distances))])
    return clusters

This is adapted from the algorithm as found on Wikipedia:

Choose one center uniformly at random from among the data points.

For each data point x, compute D(x), the distance between x and the nearest center that has already been chosen.

Choose one new data point at random as a new center, using a weighted probability distribution where a point x is chosen with probability proportional to D(x)2.

Repeat Steps 2 and 3 until k centers have been chosen.

Now that the initial centers have been chosen, proceed using standard k-means clustering.

The difference is the centroids are chosen such that it is the furthest distance, not a probability to choose between furthest distances.

My intention is to compare the Dunn Index over different values of k, and empirically the Dunn Index being higher means better clustering. I can't collect (good) data if half of the time it doesn't work, so my results are skewed due to the faultiness of k-means++ or my implementation thereof.

What other initialization strategies can be employed to get a more consistent result?