The Fermi-surfaces and Elliott-Yafet spin-mixing parameter (EYP) of several elemental metals are studied by emph{ab initio} calculations. We focus first on the anisotropy of the EYP as a function of the direction of the spin-quantization axis [Phys.~Rev.~Lett. textbf{109}, 236603 (2012)]. We analyze in detail the origin of the gigantic anisotropy in $5d$ hcp metals as compared to $5d$ cubic metals by band-structure calculations and discuss the stability of our results against an applied magnetic field. We further present calculations of light (4$d$ and 3$d$) hcp crystals, where we find a huge increase of the EYP anisotropy, reaching colossal values as large as $6000%$ in hcp Ti. We attribute these findings to the reduced strength of spin-orbit coupling, which promotes the anisotropic spin-flip hot loops at the Fermi surface. In order to conduct these investigations, we developed an adapted tetrahedron-based method for the precise calculation of Fermi surfaces of complicated shape and accurate Fermi-surface integrals within the full-potential relativistic Korringa-Kohn-Rostoker Green-function method.