I believe any website that is behind the walled garden should be deindexed by Google and other search engines. Whether it's a newspaper, Q/A websites, social media, or anything else. It's only fair. When users search for something, they should only get results of web pages whose content is accessible to all without having to sign up for an account.
I've wondered recently if this simple (but powerful) feature would be enough of a differentiator for a search engine challenger to gain serious market share.
Google should be returning the highest quality results. If thats a paywalled newspaper, it should not be excluded.
However, I do think some kind of tag, similar to [AD] could appear next to the result, warning you not to click it, [PW] or [LW] for paywall and loginwall.
If I continue to run into the same paywall, I would consider buying into it. If I bought content, I would want it to show up in search. I wouldnt know I want to buy it, if I dont run into it first.
Then Google should work on a way to connect your purchase with their system or give you ability to inform them you’ve purchased a subscription so that only you get to see search results from that paywalled website, and not others.