I've seen that "tracking in exchange for free service" notion around HN a bit before, it sort of makes sense. But what about the case when you're paying for everything and still getting tracked?

I think most people expect tracking by the website that they're on, and ONLY that website. That's mainly for improving the website experience and so on. It wouldn't be a privacy violation since it's only their behavior for that website specifically, and no behavior from the other websites.

So in reality we're talking about websites that allow third party tracking or sell tracking information to third parties. That's a privacy violation.