If the cryo organization fails, it's too easy for all paper and digital records of the grave to be lost.

You could handle this by having each separate cryonic organization exchange data about locations of grave sites. The probability that they will all fail is much lower than any single one failing. Moreover, the most likely situations resulting in such large scale failure will be situations where the human economy is so damaged that replacing the liquid nitrogen will not be feasible.