In that case, wouldn't the 200x200px square with the anomaly still be highlighted as unique from the rest of the sand, since none of the sand would match it?

If I were implementing this for NASA, I'd run the analysis a number of times using different patches for my samples. Any areas that come up as anomalies more than once are probably worth checking out.

You can choose patches randomly, but they probably also have good enough telemetry and modeling to be able to predict which areas in any given picture are going to show part of the rover. That data can be used to ensure that your random patches don't include rover parts.

Only, he could see the 200x200x square sample, and tell that it was just common sand, before picking it as representative of the sand for analysis.