1.
If "No Free Lunch" means that artificial intelligence is impossible, it must also
mean that non-artificial intelligence is impossible.  Barring the intervention of
mysticism or the aether, artificial and natural learning agents are not, in
principle, different.  That is, the human brain is a kind of learning program.  If
learning programs are never intelligent, it follows that humans are never
intelligent.  Most humans would reject this conclusion, and the argument fails by
reductio ad absurdum.  If the premises lead inevitably to a false conclusion, they
must be false themselves.

Relatedly, lay definitions of intelligence do not require an intelligent actor to be
capable of solving all imaginable kinds of problems.  Humans may never understand
every facet of the natural world, even with an eternity to study it.  This doesn't
rob the species of intelligence.

2.
Following Russell's and Norvig's definition of AI as rational agency, Deep Blue is
AI.  The program behaves rationally, or near enough--no irrational player could beat
a grandmaster.  Deep Blue is AI in most senses of the term--the program acts
rationally (i.e. plays well), thinks rationally (i.e. uses a sound strategy to
explore the state space), and behaves like a human--or even better.  Deep Blue does
not think like a human:  it does not use heuristics or learn from earlier games or
study chess manuals.  But why should it?  Iterative deepening works well enough, and
it is far from clear why any other solution would be better.  A human capable of
playing chess as Deep Blue does--eschewing intuition, considering tens of thousands
of moves--would be considered dazzlingly intelligent.  It seems unfair to hold
computers to a higher standard.