IIRC the proof works by showing that the variance decreases in each step.
And as there only is a finite number of possible assignments (and they are an ordered set, ordered by variance), it thus must stop at some point. Nothing very spectacular, actually. I don't know if there is a convergence proof for fuzzy c-means or EM that have an infinite number of possible states.
Which BTW is why k-Means doesn't work with arbitrary distance functions: recomputing the means is reducing the distances for Euclidean, but may not work for other distance functions. However if it doesn't hold that the mean reduces variance, then the convergence proof fails.
You might be interested in this recent G+ post: https://plus.google.com/u/0/101988970685633977359/posts/PNGY1mZZn9E which is also about a k-means variation with size constraints.