Multi-exponential relaxation and concomitant relaxation allowed multiple quantum coherence among methyl protons in paramagnetic proteins arising from cross-correlation between Curie spin relaxation (CSR) and dipolar relaxation (DD) are investigated. Numerical simulations and semi-quantitative multi-quantum experiments in the cyanide-inhibited paramagnetic protein horseradish peroxidase underscore the presence of CSR X DD cross-terms. The magnitude of the resulting two-spin order depends on the distance and relative orientation of the methyl axis to the paramagnetic centre which can be exploited to derive structural constraints.