We report calculations of Delbrück scattering that include all-order Coulomb corrections for photon energies above the threshold of electron-positron pair creation. Our approach is based on the application of the Dirac-Coulomb Green's function and accounts for the interaction between the virtual electron-positron pair and the nucleus to all orders in the nuclear binding strength parameter αZ. Practical calculations are performed for the scattering of 2.754 MeV photons off plutonium atoms. We find that including the Coulomb corrections enhances the scattering cross section by up to 50% in this case. The obtained results resolve the long-standing discrepancy between experimental data and theoretical predictions and demonstrate that an accurate treatment of the Coulomb corrections is crucial for the interpretation of existing and guidance of future Delbrück scattering experiments on heavy atoms.