Z axes reference gets "forgotten"

I'm having a problem where after I zero-out the Z axis, some of the time, it seems to be "forgotten" when I run the program. Before running the program, I can jog to (0, 0, 0) and the tool tip is in the right place, but when I run the program, the tool either cuts way above (annoying, but no harm) or way below where it should (crash, piece ruined). I can't quite put my finger on workarounds like re-setting Z, re-loading the program, etc. Often the second time I run the program is works fine. The X and Y setting is always fine.
What could be going on here?
What can I do to get to the root cause?
All ideas are welcome. Thanks