There is a well-known way to stop Google from indexing a site, called "robots.txt", an opt-out mechanism. Since newspapers are basically advertisers these days (whose lunch is being eaten by those with better business models), and advertisers are all about "opt out" rather than "opt in", I'd say this is a case of live by the sword, get cut by the sword.

The paper is at fault for not opting out in the first place. As for the deep-link argument, it's technically trivial to stop deep linking. So again, the paper's fault.

I say let them bear the brunt of the vitriol, just for being incompetent idiots.