Are epigenetic modifications the most stable mechanisms for cell differentiation?
Epigenetic marks are reversible (you might be aware of induced pluripotent cells). Many animals can regenerate organs with high tissue complexity (such as a limb) and this involves de-differentiation in some species (Sandoval-Guzman et al., 2014). Even otherwise, cells can respond to extracellular/environmental cues to modify their epigenetic state (for e.g. EMT involved in wound healing). I would still consider epigenetic marks to be more "stable" than simple regulatory mechanisms.

Only way for a cell's identity to actually become 'locked in' is by genetic changes. The maturation of lymphocytes (especially the B-cells), would be a good example. These genetic changes happen via V(D)J recombination, class-switching recombination and somatic hypermutation. 

L1 retrotransposons are also known to contribute to somatic heterogeneity in the brain neurons. However, the frequency of insertions is not very high (Evrony et al., 2012).