Being able to predict and understand the behaviour of soft magnetic materials paves the way to their technological applications. In this study we analyse the magnetic response of soft magnetic elastomers (SMEs) with magnetically hard particles. We present experimental evidence of a difference between the first and next magnetisation loops exhibited by these SMEs, which depends non-monotonically on the interplay between the rigidity of the polymer matrix, its mechanical coupling with the particles, and the magnetic interactions in the system. In order to explain the microstructural mechanism behind this behaviour, we used a minimal computer simulation model whose results evidence the importance of irreversible matrix deformations due to both translations and rotations of the particles. To confirm the simulation findings, computed tomography (CT) was used. We conclude that the initial exposure to the field triggers the inelastic matrix relaxation in the SMEs, as particles attempt to reorient. However, once the necessary degree of freedom is achieved, both the rotations and the magnetisation behaviour become stationary. We expect this scenario not only to be limited to the materials studied here, but also to apply to a broader class of hybrid SMEs.