I think I know exactly why this is happening and there will be an added option for kmeans in due course that will make it much less likely.
(The non-deterministic part of k-means is how the cluster centroids are initialized. Currently the object uses an initialization scheme called random partition. Sometimes this can fail with empty clusters, especially on data distributions that are pathological for it. Work is already part done to offer some different initialization options).
As to how to handle empty clusters. I think sklearn actually tries to fix them as it goes, but I’ll need to check again. But, failing that, I guess we could look at adding a warning, or implementing some kind of cluster quality metric you could query the object for.