You are absolutely right. Punching "extra holes" in puzzles of certain hardness should make backtracking not as viable. But we'll loose the unique solution property.

Might make it more interesting? And maybe even bias it towards human-abilities. I think intuitively we're better at solving when the possibilities are more than 1 (just a conjecture.)