In most worlds, the oldest state just gets thrown out; you keep playing as usual, it's just that if you were then to try and rewind all the way to the beginning, there would be a limit on how far you can go.

In world 4, though, where you can walk to the beginning of time just by walking to the leftmost part of the level, I actually kick the player out of the level when there's no more memory. I have never heard of anyone noticing this.

Theoretically, you probably just want to kick the stuff at the end out. (i.e. you lose the earliest state you can)

That would be a cool game mechanic: you can freeze time and fine tune your behavior over a small window of the immediate past(e.g. the last two seconds), with the ability to see how the game changes over that window "strobe style." Sort of like Sherlock Holmes (in the movie where he thinks everything through "what if" style).

That's basically the mechanic in the game Frozen Synapse: http://www.frozensynapse.com/

Every player plans their movements for the next fraction of a second and all turns get executed simultaneously.

I was thinking of a one player game against the computer, so the player can actually see what the computer will do according to their planned action.