I got this problem from Rustan Leino, whom Tom Ball told (a close variation of) this problem.
The problem has been featured as a Car Talk Puzzler under the name "Prison Switcharoo". But, if you can find that page, beware: the Car Talk problem page also contains an answer.
I solved it and wrote up my solution.
$N$ prisoners get together to decide on a strategy. Then, each prisoner is taken to his own isolated cell. A prison guard goes to a cell and takes its prisoner to a room where there's a switch. The switch can either be up or down. The prisoner is allowed to inspect the state of the switch and then has the option of flicking the switch. The prisoner is then taken back to his cell. The prison guard repeats this process infinitely often, each time choosing fairly among the prisoners. That is, the prison guard will choose each prisoner infinitely often.
At any time, any prisoner can exclaim "Now, every prisoner has been in the room with the switch." If, at that time, the statement is correct, all prisoners are set free; if the statement is not correct, all prisoners are immediately executed. What strategy should the prisoners use to ensure their eventual freedom?
If $N = 1$, the prisoner can just make the exclamation upon entering the room with the switch. So, we'll assume from now on that $N > 1$.
The prisoners should choose one of themselves to act as the downer. The rest will act as uppers.
Each upper does the following. If the switch is down when he enters the room, he flips the switch up, unless he's already flipped the switch up twice.
The downer does the following. If the switch is up when he enters the room, he flips the switch down. Then, if he's flipped the switch down $2N-2$ times, he makes the exclamation.
First, we need to show that this strategy is safe, i.e., that the exclamation will never be made when it will cause the prisoners to die. Second, we need to show that it's live, i.e., that eventually the exclamation will be made.
Here's why the strategy is safe. Suppose that the downer is in the room, but fewer than $N$ prisoners have ever been to the room. The downer has been in the room, so this means that fewer than $N-1$ uppers have been to the room, i.e., at most $N-2$ uppers have been to the room. Each of these uppers can have flipped the switch up at most twice, so the number of up-flips so far is at most $2(N-2)$. Each down-flip can only occur after an up-flip, except for the very first down-flip which might occur just because the switch started out up. Thus, the number of down-flips so far is at most $2(N-2)+1 = 2N-3$. The downer only makes the exclamation if his down-flip count is at least $2N-2$, so he can't make an exclamation in this situation. Thus, the exclamation is never made when fewer than $N$ prisoners have been to the room.
Here's why the strategy is live. First, we'll show that whenever the down-flip count is less than $2N-2$, at some future point it must increase by one. There are two cases to consider when the down-flip count is less than $2N-2$.
This covers all the cases, so we know that whenever the down-flip count is less than $2N-2$, it will eventually increase by one. Thus, eventually the down-flip count reaches $2N-2$, which causes the downer to make the exclamation.