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.
Well.... As far as spying goes it doesn't sound that horrible. Since they are only checking hashes of your history against a list of common cheating site hashes they really gain minimal information. If their were clear opt-ins and transparency I would definitely be okay with this sort of anti-cheating measure.
Well to be fair, you can often receive those gorillas from reputable shippers (torrents), keep them each in their own strong cage (different user account under wine, chroot/namespaces being the next step), and prevent them from getting overexcited by the jungle (iptables).
