We study the spin-glass transition in several Ising models of relevance for quantum annealers. We extract the spin-glass critical temperature by extrapolating the pseudo-critical properties obtained with Replica-Exchange Monte-Carlo for finite-size systems. We find a spin-glass phase for some random lattices (random-regular and small-world graphs) in good agreement with previous results. However, our results for the quasi-two-dimensional graphs implemented in the D-Wave annealers (Chimera, Zephyr, and Pegasus) indicate only a zero-temperature spin-glass state as their pseudo-critical temperature systematically drifts towards smaller values. Thus, the asymptotic runtime to find the low-energy configuration of those graphs is likely to be polynomial in system size. Nevertheless, this scaling may only be reached for very large system sizes---much larger than existing annealers---, as we observe an abrupt increase in the computational cost of running replica-exchange Monte-Carlo around the point marked by the pseudo-critical points found previously. Thus, two-dimensional systems with local crossings can display enough complexity to make unfeasible the search for low-energy configurations at temperatures that can be reached in current superconducting quantum annealers.