BiVO4 (BVO) is an important photocatalytic and ferroelastic material. It has been extensively studied using density functional theory (DFT). However, on optimization, at a commonly employed level of theory using the Perdew-Burke-Ernzerhof (PBE) exchange-correlation functional, the monoclinic scheelite (ms-BVO) structure transforms into a higher-symmetry tetragonal scheelite (ts-BVO) phase spontaneously, which has also been confirmed by other groups. Such a transformation is highly unusual, as one would expect the transition to a lower symmetry structure to be modeled well at this level of theory, as is the case with, for example, the perovskite BaTiO3, and hints at a subtle interplay between structural and electronic properties. In this work, we demonstrate that this phase transition nevertheless can be described accurately with DFT but only using a hybrid density functional with ∼60% Hartree-Fock (HF) exchange. We find a soft phonon mode in ts-BVO, which corresponds to the phase transition from ts-BVO to ms-BVO associated with a double-well potential characterizing this phase transition, implying that the transition is of the second order. We find two key factors that can explain this surprising behavior. First, the polarizability of the Bi3+ ion, with an on-site contribution from the hybridization of its 6s and 6p states, is notably underestimated by DFT. Moreover, the effective radius of the Bi3+ ion proves to be too large. With the 60% HF exchange hybrid functional, the description of the polarizability of Bi3+ does not improve but the radii of the Bi3+ ions approach more realistic values. The polarizability of the O and V ions are reasonably described already by PBE. To gain further insight into the problem, we investigated the structural stability of other ABO4 oxides, including ScVO4, LaNbO4, YTaO4, and CaWO4, and related materials. Some of them have similar behavior to BVO, whose ground-state monoclinic structure proves to be unstable using commonly employed DFT approaches. In particular, for ScVO4, we found that the scheelite tetragonal and fergusonite monoclinic structures cannot be distinguished using the PBEsol functional. But the fergusonite monoclinic structure becomes stable using the hybrid functionals with high fractions of HF exchange, which points to the crucial role of the accurate ionic size reproduction by the method of choice as the on-site Sc3+ polarizability is too low to have a significant effect. Our findings would be of high interest for the study of other problematic materials with subtle size and polarization properties, especially ABO4 oxides that undergo similar phase transitions.