We report a combined X-ray photoelectron spectroscopy and atomic force microscopy study of ultrafine (<30 nm) Al/Al-oxide core-shell nanoparticles. A complex fine structure is observed within O 1s and Al 2p core-level electronic spectra of the particles, indicative of a corresponding complex system morphology. The photoemission spectra of the Al metallic core exhibited a low binding energy component, ascribed to strongly undercoordinated metallic Al atoms in the particle core. Such a fraction of undercoordinated metallic atoms grows larger in relative weight as the particles get smaller, finally becoming completely dominant for nanoparticle size below 20 nm. This feature is interpreted as the fingerprint of vacancy-cluster formation within the metallic core as an effect of oxidation. For the smallest particle size investigated (<10 nm), vacancy clusters coalesce, leading to the core disruption, with a heavy impact on the corresponding electronic and plasmonic response.