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. If he's right, they're released.

If If he says "I don't know", he can set the coin to heads or tails. The king may turn over the coin after a prisoner leaves (and before he brings the next in), but he may only do so a finite k number of times in total. (This is a key similarity to the number of lies in the problem you describe).

The prisoners may discuss a strategy before starting, but the king gets to listen in and learn their strategy. So long as the game continues, every prisoner will be picked inifinte times (i.e. every prisoner can always expect to get picked again).

Is it possible for the prisoners to guarantee their eventual release?

The answer is yes, and there's a known bound on how long it takes. (Got this from slashdot a long time ago.)

Edit: Found it. Here's the discussion that spawned it, and here's the thread that introduces this problem, and here's a comment with a solution. Apparently, the problem has a name it goes by.

Edit2: This also serves as a case study in how to present a problem as succinctly as possible. The only thing I got wrong about its statement was that the king chooses the order of the prisoners going into the CC (rather than it being random), although given the constraint that each prisoner is eventually brought in infinite times, and the strategy must work all the time, I don't think it changes the problem.