The structure of solids and their phases is mainly determined by static Coulomb forces while the coupling of charges to the dynamical, i.e., quantized degrees of freedom of the electromagnetic field plays only a secondary role. Recently, it has been speculated that this general rule can be overcome in the context of cavity quantum electrodynamics (QED), where the coupling of dipoles to a single field mode can be dramatically enhanced. Here we present a first exact analysis of the ground states of a dipolar cavity QED system in the non-perturbative coupling regime, where electrostatic and dynamical interactions play an equally important role. Specifically, we show how strong and long-range vacuum fluctuations modify the states of dipolar matter and induce novel phases with unusual properties. Beyond a purely fundamental interest, these general mechanisms can be important for potential applications, ranging from cavity-assisted chemistry to quantum technologies based on ultrastrongly coupled circuit QED systems.