The eHow link would never fly in a National Park - soaking the rock in paint thinner, then hosing it onto the ground.
The second link is mostly about painting over graffiti, but it mentions an interesting product - Motsenbocker’s Lift Off #4. Its a water based biodegradable solvent that is highly rated, apparently even works for removing acrylic paint on stone.
Still thinking they should wipe the paint off with hand labor and rags rather than hosing it onto the ground. Even with a biodegradable solvent, the paint/solvent mixture may still be toxic.
Then there's the pressure washer, but it would take some skilled labor. The paint laden runoff would probably have to be collected somehow, and a careless operator could damage soft rock.
