I think you have identified better solutions than the current ones. What is more interesting is that many underlying processes already exist, for example any gmail address can be "customized" by adding "+<string>" to the end, Google ignores the +string and delivers it anyway. You can then filter on email sent to the +string value. Not everyone however accepts an email with + in the name part. Paypal has the ability to send you out to Paypal to authorize a payment, the vendor never sees your banking details. Their API works well and could be adopted by any bank if they chose. At Blekko we separated queries from IP addresses, from userid (if they were logged in). You could do it, still get ranking training data from it, and be completely unable to turn over "the last week of searches from this IP" to federal agencies. That was driven by the CTO.

So at the end of the day there is a lot of things which make data toxic easily avoidable, and it takes people at the company willing to invest in making the data "non-toxic" and to some extent non-useful to people outside the company.