Perception is everything. I suspect many Google users will "hear" Google is storing your search history. Unless Google does a VERY good job of explaining how this actually works, many users will quit using google at home to search for ...well you know... for fear their boss can somehow find out. After all they know the company advertises on Google so maybe they can get access. Now most reasonably knowledgable web savy persons will know this is not the case. But with the general population things have a way of getting lost in translation. Word of mouth is both the best and worst form of advertising. In this case if the public gets anything less than "the whole story" they will have perceived security issues. It doesn't have to be true to have an affect. When it comes to privacy and security I think everyone would agree that you should always err on the side of caution. Even the discussion of privacy issues with Google will lead some to play it safe and switch engines. People will more often than not only get half the story in this case it raises concerns justified or not.