You could mitigate that by adding a limited, rotating color pallet. every time pixels are locked two colors are taken away and two different colors are added. You would always be able to see beforehand when certain colors would be made available, enabling a new level of planing. It also forces creative solutions in defending your art

That idea would even work standalone without the immutable thing