If you read the linked thread, they are not "accessing your browser history". Rather, as a specific countermeasure against specific cheats, they checked the DNS cache for access to a particular set of phone-home server addresses embedded in some cheats. Not websites, but backend servers (ironically) enforcing DRM for cheat software. Like all such countermeasures, it was effective for a short while, then counter-countered by the cheat. What they sent back to valve was only a "yes they appeared to have accessed cheat backend server X", not a list of all accessed servers or browsing history.
I'm not saying I love it, but it's important to be accurate before turning the outrage dial to 11.
So far as outsiders were able to tell, it sent back hashes of every DNS cache entry. Someone stuffed their DNS cache with a larger-than-usual number of entries and found the amount of encrypted data sent back consistently increased by exactly the amount required to send every hash twice, then went back to normal when they cleared their DNS cache.
This is worse than checking history in some ways. It's much easier to get a stray entry in your DNS cache than to accidentally visit a "bad" website (which isn't that hard either). If anyone links to an image on that domain's servers, Valve will use the presence of the domain in the resolver cache as evidence that you're a cheater. That's not a very reliable system, and I don't think it justifies the privacy invasion from either perspective.
I'm not saying I love it, but it's important to be accurate before turning the outrage dial to 11.