Random lasers are optical sources where light is amplified by stimulated emission along random paths through an amplifying scattering medium. Connections between their physics and the one of quenched disordered nonlinear systems, notably spin glasses, have been recently suggested. Here we report a first experimental study of correlations of spectral fluctuations intensity in a random laser medium where the scatterers displacement significantly changes among consecutive shots. Remarkably, our results reveal that the replica symmetry breaking (RSB) phenomenology is robust with respect to an averaging over different realizations of the disorder. Moreover, besides opening new intriguing questions about the understanding of such a phenomenon, this work aims to clarify the connection between the RSB with the onset of the Lévy regime, i.e. the fluctuations regime that is a peculiar feature of the random lasing under critical conditions. Our results suggest that the former occurs independently of the latter and then the RSB phenomenology is a generic feature linked to the random laser threshold.