I have the images of cartoons, that were compressed. The example:

They have such noise, that is not easy to delete.

Even though the pixels are on the gray background, the noise pixels can be of very different colors and if I look at the histogram (of grayscale image) of such image I see a lot of bins around the bin of main color. But I can't just delete the colors of value, that are not of main color, because there is a risk to delete some important features (as eye, for example). Also I've tried to posterize image (example presents 8 colors), but some pixels still remain.

Also I've tried median filter, but it is not able to vanish such heavy noise ( I use 3*3 filter).
Please, give some methods that can effectively remove the noise in this case. I would be grateful for any help!