Interesting stuff, games seem like an ideal target for such recording, because their data is available offline and they are by nature event-focused.
I wonder how/if this could be applied to network-facing software like a daemon, or programs that transform large amounts of data.
I forgot to mention that we actually found a lot of bugs by seeing a playback diverge from the original recording; this was often due to uninitialized variables or reading from random memory. We could generally see when the divergence happened because we computed a checksum of the state of the world every frame and stored it in the recording as well.