I don't view that as a problem -- at least, as a problem that can be solved more than very temporarily.
We used to have (at least) three domains: public, private, and secret. The private domain was clearly under attack by networks and data processing decades ago, but it was thought that laws and care could combat it successfully. Around the early to middle 1990s, it became clear that this wasn't working, and that ordinary progress was going to push private things into the public sphere. Some people (the cypherpunks) thought that the way to resolve this was to move private things into the secret sphere, via public key crypto. That could have worked for a while, but it eventually would have failed in the same way that laws and "just be careful" were already failing, and it didn't matter, in any case, since the vast majority of people never bought into the need.
Today, I believe that it's clear that virtually everything now in the private domain will soon become public, and that there's not really anything that can be done about it. I'm increasingly of the opinion that the problems associated with losing privacy to the public are less severe than the problems of losing what should be public to the secret, insofar as it's possible.
So, basically, clearing your browser history is like plugging a hole in a sieve: the only way to actually stop the leakage is to wall yourself off from the world, a cure worse than the disease. Instead, I think we should focus on keeping secret things that need to be secret, and abandon the merely private to the public sphere. With the increasing proliferation of wireless cameras and microphones, and software that the vast majority of users do not understand, privacy is a lost cause.
Begin acting now as though everything you do is public -- it's the only safe thing to do.
That's only a problem here b/c in the past it has been used more for mischief than for good. There are a ton of good applications for using a browser history to enhance the user experience. As we see more of these in the future, attitudes will change.
