Arrested soft materials such as gels and glasses exhibit a slow stress relaxation with a broad distribution of relaxation times in response to linear mechanical perturbations. Although this macroscopic stress relaxation is an essential feature in the application of arrested systems as structural materials, consumer products, foods, and biological materials, the microscopic origins of this relaxation remain poorly understood. Here, we elucidate the microscopic dynamics underlying the stress relaxation of such arrested soft materials under both quiescent and mechanically perturbed conditions through X-ray photon correlation spectroscopy. By studying the dynamics of a model associative gel system that undergoes dynamical arrest in the absence of aging effects, we show that the mean stress relaxation time measured from linear rheometry is directly correlated to the quiescent superdiffusive dynamics of the microscopic clusters, which are governed by a buildup of internal stresses during arrest. We also show that perturbing the system via small mechanical deformations can result in large intermittent fluctuations in the form of avalanches, which give rise to a broad non-Gaussian spectrum of relaxation modes at short times that is observed in stress relaxation measurements. These findings suggest that the linear viscoelastic stress relaxation in arrested soft materials may be governed by nonlinear phenomena involving an interplay of internal stress relaxations and perturbation-induced intermittent avalanches.