The United Kingdom has a law (Data Protection Act (1984)) whose main point is to prevent companies from building those sort of databases. If you hold personal data about an individual you are under a legal obligation to to allow access to that individual access to that data so that they can check it is accurate, guarentee its security and you have have a good story on the information's relavance.
Obviously, this was all put in place before the Internet so its all a bit pointless, but I guess where the BBC is coming from is that, to UK ears, googles policy of storing your search history feels contrary to the law.