Although it is quite egregious here - this is not a problem inherent to colorization but rather to generative models in general.

Using something akin to a variational autoencoder would solve this problem, because it learns a distributional approximation rather than a single point estimate of the color, and then the random noise vector input allows one to sample from this output distribution. Similarly, Mixture Density Networks allow you to model a distribution and then sample from it.