We report results of a search for supersymmetry (SUSY) with gauge-mediated symmetry breaking in di-photon events collected by the D0 experiment at the Fermilab Tevatron Collider in 2002--2006. In 1.1 fb$^{-1}$ of data, we find no significant excess beyond the background expected from the standard model and set the most stringent lower limits to date for a standard benchmark model on the lightest neutralino and chargino masses of 125 GeV and 229 GeV, respectively, at 95% confidence.