We compute for the first time the long-distance penguin contribution to the double radiative B-meson decays by applying the perturbative factorization theorem. The numerically dominant penguin amplitude arises from the soft-gluon radiation off the light up-quark loop rather than the counterpart charm-loop effect. Importantly, the long-distance up-quark penguin contribution brings about the substantial cancellation of the known factorizable power correction, thus enabling B_{d,s}→γγ to become new benchmark probes of physics beyond the standard model.