Your mail analogy is useful here, but I come to the opposite conclusion you do.

In the US, in order to accept mail for someone else, and open that mail, they would have to be your registered agent for that purpose. This requires a signed and notarized form (1583; "Application for Delivery of Mail by an Agent"). A contract won't actually enable that to happen legally.

So, your example of Lenovo having a click-through EULA for this breaks down if you want to compare it to mail handling in the US. If SSL communication were subject to the same protections as mail (as I think it should be, though computer privacy law is much messier and less well-defined at this point in history), what Lenovo is doing would be illegal even with a signed contract, and given that click-through EULAs are questionably binding in some jurisdictions, it becomes very shaky ground. Of course there is no legal form for being a registered agent for SSL communications, and that would complicate things like proxies at businesses (though the expectation of privacy while at work as been tested in court a few times and there are some reasonably stable expectations, and proxies are fine).

In short, I believe we're in a state of flux because none of this stuff has been tested in court and the legislature at various levels simply don't have the expertise to cope with the new landscape. But, while you're taking a pro-business libertarian approach, I'm taking a pro-individual civil libertarian approach. If the state has a legitimate purpose (and I'm not necessarily arguing that it does), it is to defend individuals from more powerful people and groups. Corporations and rogue state entities (including those in the US) are the "gangs" we currently have to contend with, and I think law should reflect that reality. A contract between entities with vastly different power to negotiate is less valid, in my eyes, than a contract between equals. i.e. a contract between a sharecropper and the land owner should probably be viewed with suspicion, as the land owner often holds vastly more power over the sharecropper than vice versa (for example, land owners had sheriffs in their employ, enabling the use of semi-legal force to impose their will).

This stuff is complicated, and I don't believe one can simplify it out of existence by saying, "The buyer of this laptop agreed to it, so it's on them." I'm pretty confident that Lenovo didn't advertise this "feature", so buyers would only find out after they'd bought it. And, I'm also confident (based on research) that almost nobody reads the EULA, and Lenovo were betting on that fact. They knew this was shady as fuck, and chose to do it anyway. 95% of their customers had no clue what was happening to them, because Lenovo and Superfish went to lengths to hide it from them.

"It may be a bit sleazy, but it's not fundamentally wrong."

I disagree.

"Note that neither the Lenovo valet service or the incompetent mail handler are actually maliciously trying to harm you"

I disagree with this as well. Lenovo and Superfish are behaving with malicious intent, even without the gaping security flaw.

Unless they put it in clear wording on the packaging and the website and in the product description that this product is subsidized by user-tracking ads (as the Amazon Kindle offers two versions of their product, one with ads one without, at different prices), they are misleading consumers.