During the last decade it has become evident that the magnetorotational instability is at the heart of the enhanced angular momentum transport in weakly magnetized accretion disks around neutron stars and black holes. In this paper, we investigate the local linear stability of differentially rotating, magnetized flows and the evolution of the magnetorotational instability beyond the weak-field limit. We show that, when superthermal toroidal fields are considered, the effects of both compressibility and magnetic tension forces, which are related to the curvature of toroidal field lines, should be taken fully into account. We demonstrate that the presence of a strong toroidal component in the magnetic field plays a non-trivial role. When strong fields are considered, the strength of the toroidal magnetic field not only modifies the growth rates of the unstable modes but also determines which modes are subject to instabilities. We find that, for rotating configurations with Keplerian laws, the magnetorotational instability is stabilized at low wavenumbers for toroidal Alfven speeds exceeding the geometric mean of the sound speed and the rotational speed. We discuss the significance of our findings for the stability of cold, magnetically dominated, rotating fluids and argue that, for these systems, the curvature of toroidal field lines cannot be neglected even when short wavelength perturbations are considered. We also comment on the implications of our results for the validity of shearing box simulations in which superthermal toroidal fields are generated.