Exacty what I was thinking.
Some years ago I also tried this and had great results by just resizing the image first to something like 100x100 pixels.
we got good results for that specific failure mode with random sampling.
how much samples to take require some tuning, but you can use the image data itself to facilitate the tuning part by exiting the random sampling when the deviation of sampled pixels is below a factor proportional to samples/totals