In the rich phase diagram of ${\mathrm{Na}}_{x}{\mathrm{CoO}}_{2}$, $x=0.71$ enjoys special stability and is called the Curie-Weiss metal due to its anomalous properties. Similarly, $x=0.84$ prepared from high temperature melt is a special end point beyond which the system phase separates. Using synchrotron x-ray diffraction on single crystals, we discovered $\sqrt{12}a$ and $\sqrt{13}a$ superlattice structures which we interpret as the ordering of Na (vacancy) clusters. These results lead to a picture of coexisting local moments and itinerant carriers and form the first step towards understanding the many anomalous properties of cobaltates.