[geocar]

> Say an employee leaves, they should have the right to have records removed.

Not exactly. They have the right to be forgotten which is slightly different, and the company has certain rights to keep those records. Recital 65 is quite broad and allows a company to remember that it hired (or fired) someone because it may need this information to protect against legal claims, or to pay taxes correctly (i.e. another legal obligation). It would seem to permit private blockchains, and (at least in some cases) public blockchains.

http://www.privacy-regulation.eu/en/recital-65-GDPR.htm