The magneto-optical polarization rotation effect has prolific applications in various research areas spanning the scientific spectrum including space and interstellar research, nano-technology and material science, biomedical imaging, and sub-atomic particle research. In nonlinear magneto-optical rotation (NMOR), the intensity of a linearly-polarized probe field affects the rotation of its own polarization plane while propagating in a magnetized medium. However, typical NMOR signals of conventional single-beam $Lambda-$scheme atomic magnetometers are peculiarly small, requiring sophisticated magnetic shielding under complex operational conditions. Here, we show the presence of an energy-symmetry blockade that undermines the NMOR effect in conventional single-beam $Lambda-$scheme atomic magnetometers. We further demonstrate, both experimentally and theoretically, an inelastic wave-mixing technique that breaks this NMOR blockade, resulting in more than five orders of magnitude ($>$300,000-fold) NMOR optical signal power spectral density enhancement never before seen with conventional single-beam $Lambda-$scheme atomic magnetometers. This new technique, demonstrated with substantially reduced light intensities, may lead to many applications, especially in the field of bio-magnetism and high-resolution low-field magnetic imaging.