It is certainly a contentious thing. A consideration, though, is that if they're preserving the rock face by not drilling bolts into it, then what are they preserving it for? I wonder if you can even see the bolts from the ground (I doubt it).
Don't you think there's any worth in preserving the natural environment for its own sake? It sounds like you're saying if you can't put bolts into the rock to climb it then the rock is worthless and shouldn't be preserved anyway.
Maybe if you can't climb something without permanently defacing it then you should just not climb it.
The general idea is that at some point in the future, we might be able to protect these difficult routes. So we preserve it for that. This argument is more legitimate in some cases than others. For instance, maybe someday we'll have some non-destructive way to protect thin cracks and flakes. But it is very unlikely that we can say the same about a barren face.
The concept of "fair means" is based on the idea of setting limits on the artificial aids that a climber uses to reach the top. For example, pretty much every climber agrees that taking a helicopter to the top is not fair means.
It's context-specific, too. On El Cap, taking the hiking trail up the back to reach the top is not considered a "climb" on par with ascending the cliff. But on Mount Rainier, hiking the top counts as a climb even if you take the easiest way up (basically because the easiest way up is still not easy).
Free climbing itself is actually a form of fair means--ascending the rock using only what the rock itself gives you for progress. All gear does is provide a safety net.
Climbing without bolts and pitons--known as climbing "clean"--is also a form of fair means. It takes as its guiding principle to leave the rock as you found it. Under this approach, climbers will indeed leave blank faces unclimbed. Those bold enough to climb such faces with minimal protection are respected as having shown great commitment to their ideals.