(No, it is not a sufficient counter argument to say that they just spend because everyone else does; if advertising really didn't work there would no forces holding it up, and a lot of forces pushing it down. If you flipped a switch and made it not work somehow right now, advertising would be gone within a handful of years, if not faster.)
So direct response campaigns existed before google b/c there was some value holding it up; Google just came along and revolutionized it. That's part of their power from the advertisers POV -- metrics.
Large, nationwide branding campaigns have been effective b/c the entry cost to run one means they are only feasible to large corporations. And those corps have the resources to run the market surveys that are really necessary to evaluate the effectiveness of a campaign. Smaller ad budgets just can't do the followup efficacy measurements.
I definitely think both direct and branding based advertising works. I wonder if Facebook's play will be to revolutionize large branding campaigns, while google focused on the direct response (CPC v CPM, at its core).
If I were to argue that advertising works, I'd argue that it affects social proof; no one drives a Mercedes Benz because it is a functionally superior car. In the American market, products aren't purchased on their functionality, but on the social class they put you in. (Would argue a similar argument for non-luxury items, but it'd tl;dr.)