I wrote about it in a thread here called: "Why bugs might feel “impossible”" about two months ago and someone commented that the game TerraNova (from 1996) had a fully deterministic engine.
BTW TFA say StarCraft 2 (2007) used the technique but Warcraft 3 (2003) was already using a deterministic engine. Save files for Warcraft 3 games (including multiplayer ones over the Internet) consisted in only recording the player inputs and the "tick" at which they happened. This make for tiny savefiles, even for very long games.
So basically: several of us independently discovered that technique in the nineties. There may have been games in the eighties already using such a technique but I don't know any.