A central paradigm of non-equilibrium physics concerns the dynamics of heterogeneity and disorder, impacting processes ranging from the behavior of glasses to the emergent functionality of active matter. Understanding these complex mesoscopic systems requires probing the microscopic trajectories associated with irreversible processes, the role of fluctuations and entropy growth, and the timescales on which non-equilibrium responses are ultimately maintained. Approaches that illuminate these processes in model systems may enable a more general understanding of other heterogeneous non-equilibrium phenomena, and potentially define ultimate speed and energy cost limits for information processing technologies. Here, we apply ultrafast single shot x-ray photon correlation spectroscopy to resolve the non-equilibrium, heterogeneous, and irreversible mesoscale dynamics during a light-induced phase transition. This approach defines a new way of capturing the nucleation of the induced phase, the formation of transient mesoscale defects at the boundaries of the nuclei, and the eventual annihilation of these defects, even in systems with complex polarization topologies. A non-equilibrium response spanning >10 orders of magnitude in timescales is observed, with multistep behavior similar to the plateaus observed in supercooled liquids and glasses. We show how the observed time-dependent long-time correlations can be understood in terms of the stochastic dynamics of domain walls, encoded in effective waiting-time distributions with power-law tails. This work defines new possibilities for probing the non-equilibrium and correlated dynamics of disordered and heterogeneous media.