BTW, this problem is known as the Ulam(-Renyi) problem or Ulam's searching game, and has an extensive literature (with which I'm not familiar) — the following is a survey as of 2002:

* Andrzej Pelc, *Searching games with errors--fifty years of coping with liars*, Theoretical Computer Science, Volume 270 (2002), pp. 71-109 

In particular, with 1 lie allowed, to guess a number in {1…n} where n is even, the number of queries needed is the smallest integer q which satisfies n ≤ 2<sup>q</sup>/(q+1), which for n=1000 is indeed 14.

[This paper](http://arxiv.org/abs/0705.1220) seems to have a "simple solution", but maybe others more familiar with the topic can find better references.