It's absolutely preventable, we just have to make the choice to do that.
Of course - there are 'some bits of data' that will get persisted here and there, but by enlarge, there's ways to do this:
1) Policy 2) Common ethics 3) Regulation 4) Architecture 5) Law
If it became 'policy' at most companies to address this issue, there are a number of things they could do.
If it there was awareness about this - and it was framed as a moral issue, large swaths of organizations might simply make do.
Identity/Software/Systems architecture may be able to enable this - i.e. being able to make online transactions without actually identifying oneself.
Responsible regulations and responsible law could urge companies to do this.
Obvious, it will never be fully thus - but there are a lot of things that we could do.
Starting with: any account you open, you should be able to close and have all relevant information erased, unless there is some special requirement otherwise.
This is law in some places and it's not entirely unreasonable.
If we collectively made the choice we could make the internet 'mostly' a private experience for people.