I don't know much about the problem in question, but there's a related open problem in number theory.
Suppose I am thinking of a positive integer from 1 to n. You know this and know n. You want to figure out my number but are only allowed to ask if my number is in some range you name. In this game it is easy to see that you can always find out my number in less than 1+log2 n questions.
But what if I'm allowed to lie k times for some fixed k (that you know). Then the problem becomes much more difficult. A general bound in terms of k and n is open.
This suggests to me that working out problems involving lying, even in toy models, can quickly become complicated and difficult to examine.
Are you familiar with the seemingly similar question about the prisoners, king, and coin? I don't know the name, but it goes like this:
...There are n prisoners in separate rooms, each with a doorway to a central chamber (CC) that has a coin. One by one, the king takes a random prisoner into the CC (no one else can see what is going on), and asks the prisoner if the king has brought all prisoners into the CC by now. The prisoner can either answer "yes" or "I don't know". If he says the former and is wrong, all prisoners are executed.
Here's the new thread for posting quotes, with the usual rules: