We present a detailed study of the lifetime of optical spectral holes due to population storage in Zeeman sublevels of Nd$^{3+}$:Y$_2$SiO$_5$. The lifetime is measured as a function of magnetic field strength and orientation, temperature and Nd$^{3+}$ doping concentration. At the lowest temperature of 3 K we find a general trend where the lifetime is short at low field strengths, then increases to a maximum lifetime at a few hundreds of mT, and then finally decays rapidly for high field strengths. This behaviour can be modelled with a relaxation rate dominated by Nd$^{3+}$-Nd$^{3+}$ cross relaxation at low fields and spin lattice relaxation at high magnetic fields. The maximum lifetime depends strongly on both the field strength and orientation, due to the competition between these processes and their different angular dependencies. The cross relaxation limits the maximum lifetime for concentrations as low as 30 ppm of Nd$^{3+}$ ions. By decreasing the concentration to less than 1 ppm we could completely eliminate the cross relaxation, reaching a lifetime of 3.8 s at 3~K. At higher temperatures the spectral hole lifetime is limited by the magnetic-field independent Raman and Orbach processes. In addition we show that the cross relaxation rate can be strongly reduced by creating spectrally large holes of the order of the optical inhomogeneous broadening. Our results are important for the development and design of new rare-earth-ion doped crystals for quantum information processing and narrow-band spectral filtering for biological tissue imaging.