Non-stoichiometric oxides with Ruddlesden-Popper structure type and the chemical formula A2BO4 (A = rare earth, B = transition metal) can uptake extra O-atoms on interstitial lattice sites (Oint). Due to their high mobility even at room temperature, long-range O-ordering up to the sub-mesoscale is observed in several A2BO4+d phases, which, together with charge and spin ordering, results into a competitive degree of freedom between structural and electronic ordering. Oxygen ordering thus adds an additional degree of freedom that may affect charge and spin ordering schemes, which is not present in the Sr-doped counterpart A2-xSrxBO4. In this regard, La2CoO4+d shows extremely high oxygen diffusion coefficients already at room temperature attaining diffusion coefficients of D = 1 x 10-9 cm2s-1. Combining neutron and synchrotron diffraction data, we evidenced for La2CoO4.25 a 3D modulated oxygen ordering setting in below 600°C, involving translational periodicities of more than 100 Å. Further on, a checkerboard charge ordering between Co2+/Co3+ occurs below 350°C, stabilizing a reconstructive rearrangement of the entire Oint-sublattice, showing a lock-in transition to a formal 4a x 4b x 4c ordered Ruddlesden-Popper type unit cell. The strong structural correlations induced by the sub-mesoscopic oxygen ordering are discussed to explain the unusually high oxygen mobility in terms of phonon softening.