In the rich phase diagram of NaxCoO2, 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.