The crux of the debate is whether Google is a quasi public place, like a convenience store, or something private, like your closet.
I think legally, Google is no different than any other business. Following the appropriate process, police can ask a convenience store to search their sales records to see who bought something on a particular date. They can ask a credit card company about someone's purchases on a particular date.
On the other hand, people disclose information to Google that they don't disclose to their convenience store clerk. That information is even more intimate than what people disclose to a credit card company. Someone's searches can reveal the deepest darkest things about them.
On the other other hand, Google as a service is not really one of trust. It's not like a bank that provides a safe deposit box and promises to not look inside (and is usually legally barred from doing so). Google rummages through your personal information for its own profit. Twenty years ago, if you had asked people: "If you had a service that data mined the information you gave it for advertising purposes, where potentially dozens of engineers and operators have access to that information--would you consider that a trusted and private system?" They would have said "no."