Spin relaxation of localized charge carriers in semiconductors is primarily governed by hyperfine interaction with the surrounding nuclear spin bath. While this mechanism is well-established in III-V bulk materials and quantum dots, its critical role in metal halide perovskites (MHPs) has only recently emerged. Their inverted band structure induces an unusual hierarchy of hyperfine couplings, with hole interactions dominating electron interactions, particurlaly in Pb-based perovskites. Here, we adapt a spin relaxation model - originally developed for muon spin spectroscopy - to provide an exact description of longitudinal spin relaxation for localized carriers across arbitrary hyperfine correlation times. This approach is motivated by recent experimental evidence in MAPbI3, which places carrier spins in an intermediate correlation regime, where conventional mono-exponential approximations fail. Our analysis reveals distinct hyperfine relaxation channels: electrons couple primarily to halogen nuclei, whereas holes are governed by metal nuclei. This leads to a key prediction - perovskites with lighter halogens and metal cations exhibit significantly extended spin lifetimes. Applied to time-resolved Faraday rotation data obtained from two perovskite samples, our model extracts key microscopic parameters - including the carrier localization volume and hyperfine correlation time - demonstrating the necessity of the exact dynamical solution over a single-exponential approximation. These findings provide microscopic insight into hyperfine-driven spin relaxation in MHPs and establish a robust framework for characterizing carrier localization and spin dynamics.