The initialization is supposed to be random, so does the clustering converge to the same result regardless of the initialization?
Quite the contrary. If the k-means problem were a nice, convex optimization problem, we wouldn't be randomly initializing it, since simply starting at (0,0,...,0) would give the right answer.
The reason for random initialization is exactly that you can get different solutions by trying different random seeds, then pick the best one when all your k-means runs are done. Ten runs is a good rule of thumb for many applications.
Finding the global minimum of the k-means problem is NP-hard in general. The common algorithm is really a heuristic.