Oh dear, I suppose that rules out other "cheats" then: such as prisoner n guessing after n seconds. At any point in time, only finitely many have guessed, so only finitely many have guessed wrong. Hence the prisoners can never be executed. (Though they can never be released either.)

OK, I also got a "non-cheat" solution: unfortunately, it is non-constructive and uses the Nkvbz bs Pubvpr, so it still feels like a bit of a cheat. Is there a solution which doesn't rely on that (or is it possible to show there is no solution in such a case?)