We observe a deuteron beam polarization lifetime near 1000 s in the horizontal plane of a magnetic storage ring (COSY). This long spin coherence time is maintained through a combination of beam bunching, electron cooling, sextupole field corrections, and the suppression of collective effects through beam current limits. This record lifetime is required for a storage ring search for an intrinsic electric dipole moment on the deuteron at a statistical sensitivity level approaching 10-29 e cm.