The radical pair model of the avian magnetoreceptor relies on long-lived electron spin coherence. Dephasingresulting from interactions of the spins with their fluctuating environment, is generally assumed to degrade the sensitivity of this compass to the direction of the Earth's magnetic field. Here we argue that certain spin relaxation mechanisms can enhance its performance. We focus on the flavin-tryptophan radical pair in cryptochrome, currently the only candidate magnetoreceptor molecule. Correlation functions for fluctuations in the distance between the two radicals in Arabidopsis thaliana cryptochrome 1 were obtained from molecular dynamics (MD) simulations and used to calculate the spin relaxation caused by modulation of the exchange and dipolar interactions. We find that intermediate spin relaxation rates afford substantial enhancements in the sensitivity of the reaction yields to an Earth-strength magnetic field. Supported by calculations using toy radical pair models we argue that these enhancements could be consistent with the molecular dynamics and magnetic interactions in avian cryptochromes.