Compositionally complex solid electrolyte (Li_0.375Sr_0.4375)(Ta_0.375Nb_0.375Zr_0.125Hf_0.125)O₃ (LSTNZH) samples are synthesized using different sintering temperatures, durations, and cooling conditions (furnace cooling (FC) vs. air quenching (AQ)). The temperature-dependent grain growth has been examined to investigate the microstructural evolution and the origin of exaggerated (abnormal) grain growth. At moderate temperatures, the grain growth of LSTNZH follows a cubic root growth model with an Arrhenius temperature dependence. With increasing temperature, bimodal microstructures develop, and the Arrhenius temperature dependence breaks down. Notably, increasing the temperature induces increased Nb segregation at general grain boundaries (GBs), in contrast to classical GB segregation models but suggesting premelting-like GB disordering, which can explain the observed abnormal grain growth (AGG). In addition, the large grains become faceted with increasing temperature, which occurs concurrently with the temperature-induced transitions in GB segregation and grain growth, thereby further supporting the occurrence of a GB phase-like (complexion) transition. The impacts on the densification, ionic conductivity, and hardness are also examined. This work provides a new insight into the fundamental understanding of the grain growth mechanisms of the emergent class of medium- and high-entropy compositionally complex ceramics (CCCs), which is essential for tailoring microstructures and material properties.