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 ≤ 2q/(q+1), which for n=1000 is indeed 14.
This paper seems to have a "simple solution", but maybe others more familiar with the topic can find better references.