We discuss decays of ultra-relativistic neutrinos over cosmological distances by solving the decay equation in terms of its redshift dependence. We demonstrate that there are significant conceptual differences compared to more simplified treatments of neutrino decay. For instance, the maximum distance the neutrinos have traveled is limited by the Hubble length, which means that the common belief that longer neutrino lifetimes can be probed by longer distances does not apply. As a consequence, the neutrino lifetime limit from supernova 1987A cannot be exceeded by high-energy astrophysical neutrinos. We discuss the implications for neutrino spectra and flavor ratios from gamma-ray bursts as one example of extragalactic sources, using up-to-date neutrino flux predictions. If the observation of SN 1987A implies that \nu_1 is stable and the other mass eigenstates decay with rates much smaller than their current bounds, the muon track rate can be substantially suppressed compared to the cascade rate in the region IceCube is most sensitive to. In this scenario, no gamma-ray burst neutrinos may be found using muon tracks even with the full scale experiment, whereas reliable information on high-energy astrophysical sources can only be obtained from cascade measurements. As another consequence, the recently observed two cascade event candidates at PeV energies will not be accompanied by corresponding muon tracks.