You don't start to see the full palette reassignments until Codename: ICEMAN and Colonel's Bequest in late 1989.
Hero's Quest (QfG1) would use that feature *extensively* for its rendering of day/night cycles, so it definitely exists by then. But yea... KQ4 and LSL2 definitely didn't have access to that tooling, and so you see weird stuff like this in the byte-stream.