That analogy implies you can empty out the contents whenever you want. Which is not necessarily true with search history.
There is no way of knowing that the information is actually deleted except trusting them.
Companies often face legal requirements that your data is truly gone, e.g. see the European Union's Data Protection Directive. So it's not just a pinky swear -- there is some legal force behind it. (Which happens to be true for the neighbor situation as well, so you really don't need to get pinky swears from everyone.)
> Companies often face legal requirements that your data is truly gone, e.g. see the European Union's Data Protection Directive.
Maybe that's part of the difference. In the US you have to keep records of stuff. At my company, we have to keep records for ~7 years, IIRC.