What you say is true. It's also the case that there's a lot of information that is nominally public--often for very defensible reasons--which historically took significant effort to get at and, even then, only in a very limited and manual way.
Today, a lot of that information is at least a lot more accessible to everyone (though in this case it still took a lot of work) and, furthermore, it can be mashed up with other public or semi-public data.
I'm pretty sure this is something we'll be collectively be coming to terms with for a long time.
Voter registration records being a perfect example - anyone can look up my address because the state makes it incredibly easy to pop my name into a website and there it is.
Of course, historically you could look up the address for most people through the white pages.
But that doesn't change the basic point. If you were to ask if you should be able to look up anyone's physical address by typing their name into a web page, I suspect many people would say no. Yet, here we are.
(I also suspect that many would be really shocked at the amount of info available about them from "deep web" searches much less via a $20 online background check.
Today, a lot of that information is at least a lot more accessible to everyone (though in this case it still took a lot of work) and, furthermore, it can be mashed up with other public or semi-public data.
I'm pretty sure this is something we'll be collectively be coming to terms with for a long time.