We investigate the interplay of particle number, N, and structural properties of selected clusters with N=12 up to N=562 by employing Gupta potentials parameterized for Aluminum and extensive Monte Carlo simulations. Our analysis focuses on closed shell structures with extra atoms. The latter can put the cluster under a significant stress and we argue that typically such a strained system exhibits a reduced energy barrier for (surface) diffusion of cluster atoms. Consequently, also its surface melting temperature, TS, is reduced, so that TS separates from and actually falls well below the bulk value. The proposed mechanism may be responsible for the suppression of the surface melting temperature observed in recent experiments.