Immutability is a core design goal of permissionless public blockchain systems. However, rewrites are more common than is normally understood, and the risk of rewrite, cyberattack, exploit or black swan event is also high. Taking the position that strict immutability is neither possible on these networks nor the observed reality, this paper uses thematic analysis of node operator interviews to examine the limits of immutability in light of rewrite events. The end result is a qualitative definition of the conditional immutability found on these networks, which we call Practical Immutability. This is immutability contingent on the legitimate governance demands of the network, where network stakeholders place their trust in the governance topology of a network to lend it legitimacy, and thus manage ledger state.