We show with first-principles molecular dynamics the persistence of intrinsic $langle111rangle$ Ti off-centerings for BaTiO$_3$ in its cubic paraelectric phase. Intriguingly, these are inconsistent with the known space group for this phase. Inspired by this observation, we deploy a systematic symmetry analysis to construct representative structural models in the form of supercells that satisfy a desired point symmetry but are built from the combination of lower-symmetry primitive cells. We define as structural prototypes the smallest of these that are both energetically and dynamically stable. Remarkably, two 40-atom prototypes can be identified for paraelectric BaTiO$_3$; these are also common to many other ABO$_3$ perovskites. These prototypes can offer structural models of paraelectric phases that can be used for the computational engineering of functional materials displaying such hidden order. Last, we show that the emergence of B-cation off-centerings and the consequent disappearance of the phonon instabilities is controlled by the equilibrium volume, in turn dictated by the filler A cation.