I can believe it easily. There are many millions of potential values for each element in the search and an unlimited number of elements per search. And the order matters (presumably).
Keep in mind that there are hundreds of thousands of relatively common words in English alone. At least as many relatively uncommon ones (including stuff like HackerNews). Then there are dozens of popular languages with probably hundreds of thousands of words each, millions of unique misspellings of words in every language, and numbers from a variety of common uses (dates, serial numbers, math problems, etc.).
People also search for character strings from computer code and the like when they are troubleshooting.
And it's not that hard to see instances where the average person would be tapping into all of that variety in a real-life search.
"map of 'address' in 'city'"
"concerts in 'city' on 'date'"
"'arbitrarily long song lyric, movie quote, book quote -- including errors'"
I assume the 16% are supposedf to mean 16% for distinct queries. The well-known queries and common typos are entered a lot more frequently - so a huge portion of those 16% may actually just be bored people googling for "fist-on-keyboard"
If that's the case, it's a very misleading statistic. If you have 1 million each of "facebook", "fcaebook", "facebok", "faceook", and "fakebook", and one "asdweniviwnxoemmgmejvj v fef", it's kind of spin to say "we’ve never seen 16% of the queries we see every day."
Think about all the searches that are related to current events. Assuming most of these events have never happened, that's a lot of new, unique searches.
Every time you do a google search, try to think if anyone else might have searched for it before. I do a lot of google searching for specific programming-related questions, and some of my terms are long and obscure enough that I'm fairly confident the exact query was never made before.
An additional consideration is the "dynamic" search that google implemented recently[1]. While you're typing, it'll guess what your final query is likely to be and display the results. Of course, the guess will usually be something that's been queried before, but if you are typing a completely new query then it will sometimes query a number of intermediate steps before you've finished typing. If this statistic includes queries of this sort, then this could contribute significantly to the number of new queries.
If they do 3 billion queries per day[1], that's almost 500 million new queries every day. You gotta figure most misspellings and typos are repeats..
[1] http://www.quora.com/How-many-search-queries-does-Google-ser...