The low-energy light-by-light cross section as determined by the nonlinear Euler-Heisenberg QED Lagrangian is evaluated in the presence of constant magnetic fields in the center-of-mass system of the colliding photons. This cross section has a complicated dependence on directions and polarizations. The overall magnitude decreases as the magnetic field is increased from zero, but this trend is reversed for ultrastrong magnetic fields $B\gtrsim B_c$, where the cross section eventually grows quadratically with the magnetic field strength perpendicular to the collision axis. This effect is due to interactions involving the lowest Landau level of virtual Dirac particles; it is absent in scalar QED. An even more dramatic effect is found for virtual charged vector mesons where the one-loop cross section diverges at the critical field strength due to an instability of the lowest Landau level and the possibility of the formation of a superconducting vacuum state. We also discuss (the absence of) implications for the recent observation of light-by-light scattering in heavy-ion collisions.