It sounds like you are losing steps on the downward Z motions. If you are absolutely sure that the Z is mechanically solid, then you should look at the electrical side. This starts at the parallel port, and includes the cables, break-out-board, and the actual stepper drivers. The software is not the issue. On my machine it is always mechanical, no matter how many times I think I have verified it.
It may be useful to set up a job that causes problems but offset the Z higher in Z so that the tool never touches the material. If Z remains inaccurate (ie Z offset shifts up after the job) then the problem is not load related. Could be a bad connection on the Z motion. Try swapping the entire Z wiring with X or Y : the bad connection should move to the swapped axis.
If Z offset is now constant no matter how many times you try it, the fault is load dependent, possibly a bad driver or again a bad connection (but less likely).
WarpDriver, StandingWave, Topo and gadgets available at PaulRowntree.weebly.com