There is more than one k-means algorithm.
You probably refer to Lloyds algorithm, which only depends on the initial cluster centers. But there also is MacQueen's, which depends on the sequence i.e. ordering of points. Then there is Hartigan, Wong, Forgy, ...
And of course, various implementations may have implementation and optimization differences. They may treat ties differently, too! For example, many naive implementations will always assign elements to the first or last cluster when tied. Others will preserve the current clustering assignment. So when clustering integer values, where ties are much more common, but also on the Iris data set, you may see artifacts and differences caused by this.
Furthermore, the clusters may end up being reordered by memory address after finishing k-means, so you cannot safely assume that cluster 1 remains cluster 1 even if k-means converged after the first iteration. Others will reorder clusters by cluster size (which actually makes sense for k-means, as this will more likely return the same result on different random initialization)
But assuming that all iterate Lloyd until convergence (which original MacQueen k-means didn't!) they should all at least arrive at a local optimum. There will be only oh-so-many local optima...
Consider for example the data set generated by $p_j=(\sin(2\pi \frac{j}{n}), \cos(2\pi \frac{j}{n}))$, and let $n$ be divisible by $j$. There will be a lot of local optimal solutions. Running k-means with different random seeds will indeed give your very different solutions. For appropriate parameters, I believe the chance of two different elements that were in the same cluster to be in the same cluster again in another result will be somewhere around $50\%$. In higher dimensionality, you can probably further reduce this number. For example in the $n$ dimensional data set where $p_{jj}=1$ and $p_{ij}=0$ for $i\neq j$, all points are equidistant. It's easy to see that this will cause havoc to k-means...
