Whether or not Valleywag is right depends on whether or not you believe as Valleywag does that "[s]earch engines rely on newspaper articles for more than just their news sites." In other words, does newspaper content have a material effect on the search index at Google? Would its removal effect the user experience on Google? (Note: I am only talking about Google here - clearly Google news relies on newspaper content - but given Google makes zero money directly from news search, presumably if push came to shove they could throw that product away and it would have a negligible effect on their business.)
With video, Google/ YouTube recognized two things: (1) that there was no fair use exemption to rely on - unlike hyperlinked news articles, most of the time you are watching the entire video, not a snippet; and (2) if they removed the copyrighted material their product would be much less compelling. If they didn't believe these two things, they would have told the vid providers to toss off. But they didn't want to lose the content and they couldn't finds a clear legal position to continue using it unlicensed. So what do they do? They rely on the DMCA to provide some cover for a bit while they negotiate deals to keep the content that people want in the index.
So couldn't newspapers do the same thing? Unfortunately no. First, fair use is pretty much well accepted for newspaper content - so using just the snippets is perfectly justified. As for the impact the content has on the index, it's not material in the same way video is for YouTube.
The reality is that a lot of times, for a variety of reasons (poor SEO, archival deals that keep content behind pay walls, etc.), newspaper content isn't even findable in the Google index. A far too common scenario for a newspaper is that the paper actually pays someone to go to a movie or restaurant and review it. However, the review won't even show up when someone does a keyword search on the name. But the Yelp and RottenTomoatoes reviews show up. In other words, given that newspaper content is often times unfindable in the search index, removing will have little impact, if any, on the product.
As a result, newspapers find themselves on the same playing field as the other 10 billion web pages Google indexes regularly - relying on it for distribution and very little leverage to negotiate.
UPDATE: For once I beat Fred Wilson to to the punch! ;) Albeit from a slightly different tack, Fred and I come to the same conclusion