We report the discovery of a new subclass of double-mode RR Lyrae stars in the Large and Small Magellanic Clouds. The sample of 22 pulsating stars has been extracted from the latest edition of the Optical Gravitational Lensing Experiment collection of RR Lyrae variables in the Magellanic System. The stars pulsating simultaneously in the fundamental (F) and first-overtone (1O) modes have distinctly different properties than regular double-mode RR Lyrae variables (RRd stars). The P_1O_/P_F_ period ratios of our anomalous RRd stars are within a range of 0.725-0.738, while 'classical' double-mode RR Lyrae variables have period ratios in the range of 0.742-0.748. In contrast to the typical RRd stars, in the majority of the anomalous pulsators, the F-mode amplitudes are higher than the 1O-mode amplitudes. The light curves associated with the F-mode in the anomalous RRd stars show different morphology than the light curves of, both, regular RRd stars and single-mode RRab stars. Most of the anomalous double-mode stars show long-term modulations of the amplitudes (Blazhko-like effect). Translating the period ratios into the abundance parameter, Z, we find for our stars Z{in}(0.002, 0.005) - an order of magnitude higher values than typical for RR Lyrae stars. The mass range of the RRd stars inferred from the W_I_ versus P_F_ diagram is (0.55-0.75)M_{sun}_. These parameters cannot be accounted for with single star evolution assuming a Reimers-like mass-loss. Much greater mass-loss caused by interaction with other stars is postulated. We blame the peculiar pulsation properties of our stars to the parametric resonance instability of the 1O-mode to excitation of the F- and 2O-modes as with the inferred parameters of the stars 2{omega}_1O_~={omega}_F_+{omega}_2O_.