Say you're writing a complex turn based multiplayer strategy game in the browser (i.e. JavaScript). The game state is big and complicated (think line of sight calculations in a 3d world). There can be many simultaneous games on different maps. Thus keeping all of those maps in memory on the server and verifying every single client action as it happens would quickly become prohibitively expensive. So we're faced with the situation that we cannot trust anything from the client and we cannot verify every individual client action on the server due to cost.
Has anyone experimented with recording game sessions and running offline/asynchronous verification on them as a cheat deterrent? Ideally, the players themselves would get suspicious and spot check each others' replays. Obviously there would be a significant delay between the cheat happening and the player getting flagged, but in a long-running strategy game with persistent state, I think this would be a significant disincentive.
Do you know of such examples? Have they worked well?