Lattice simulations have demonstrated that a background (electro)magnetic field reduces the chiral/deconfinement transition temperature of quantum chromodynamics for eB < 1 GeV^2. On the level of observables, this reduction manifests itself in an enhancement of the Polyakov loop and in a suppression of the light quark condensates (inverse magnetic catalysis) in the transition region. In this paper, we report on lattice simulations of 1+1+1-flavor QCD at an unprecedentedly high value of the magnetic field eB = 3.25 GeV^2. Based on the behavior of various observables, it is shown that even at this extremely strong field, inverse magnetic catalysis prevails and the transition, albeit becoming sharper, remains an analytic crossover. In addition, we develop an algorithm to directly simulate the asymptotically strong magnetic field limit of QCD. We find strong evidence for a first-order deconfinement phase transition in this limiting theory, implying the presence of a critical point in the QCD phase diagram. Based on the available lattice data, we estimate the location of the critical point.