(And everyone may have thought of this.)

Freezing kills cells largely because water expands as it freezes, rupturing cell walls, etc.

The reason water expands is that the crystalline structure traps oxygen, making for a larger volume, as instead of H2O it is H2O + O2.

Ice toward the tops of mountains is much harder than nearer the base.

On Mars, with it's less dense atmosphere, would it be possible that the "critters" got along with fewer gaseous molecules, and especially O2, and therefore when they froze there would be much less intra- and inter-cellular damage? Enabling them to survive for a relatively long period?

I dunno.

Arf