Electron spin relaxation in a spin-polarized quantum Hall state is studied. Long spin relaxation times that are at least an order of magnitude longer than those measured in previous experiments were observed and explained within the spin-exciton relaxation formalism. Absence of any dependence of the spin relaxation time on the electron temperature and on the spin-exciton density, and specific dependence on the magnetic field indicate the definite relaxation mechanism -- spin-exciton annihilation mediated by spin-orbit coupling and smooth random potential.