A novel experimental set-up was used to study superstable (magic) Ba-C(60) and K-C(60) compound clusters. The most stable systems observed cannot be rationalized by simple electronic or by geometrical shell filling arguments. Annealing the clusters past the temperature necessary for the fragmentation of the initial metastable clusters formed at the source reveals information about their thermodynamic stability. Higher temperatures yield larger species, suggesting that similar experiments may be used to rationally produce nanoscale clusters with highly desirable properties. Density functional calculations reveal ionic (K, Ba) and covalent (Ba) bonding between C(60) and the metal atoms. The entropic contribution to the Gibbs free energy is shown to be essential in determining absolute and relative cluster stabilities. In particular, we demonstrate that at higher temperatures the entropy favors the formation of larger clusters. A simple criterion which may be used to determine the absolute and relative stabilities of general multicomponent clusters is proposed.