I wonder if it would suffice to check the legality of the newest move only.
That's going to depend upon how explicit you make your notation. In Chess, for example, I have long treated castling as a King's move, though I have recently written code for handling it as a two-piece move, and I still treat en passant as just a single Pawn move without explicitly adding the capture to the notation. In Shogi, I handle moving captured pieces off the board and changing their sides automatically without including notation for it.
That's going to depend upon how explicit you make your notation. In Chess, for example, I have long treated castling as a King's move, though I have recently written code for handling it as a two-piece move, and I still treat en passant as just a single Pawn move without explicitly adding the capture to the notation. In Shogi, I handle moving captured pieces off the board and changing their sides automatically without including notation for it.