Global optimization and data-mining techniques have been used to generate the structures of Mg and Cd doped ZnO nanoclusters. The energy has been evaluated at three levels: interatomic potentials during the filtering stage, generalized gradient based (PBE) density functional theory during the refinement of structures, and hybrid (PBE0) density functional theory for the final electronic solutions used for the prediction of the cluster optical absorption spectra. The excitonic energies have been obtained using time-dependent density functional theory including asymptotic corrections. We considered three characteristic sizes of the host (ZnO)n cluster (n = 4, 6, 8) including all chemically sensible structural types as determined from their relative energy rankings and all possible dopant permutations. Thus, an exhaustive set of the solution structures could be assessed using configurational entropic contributions to the cluster free energy, which allowed us to draw a conclusion as to the oxide miscibility at this end of the size scale. With the exception of low temperature magnesium doped n = 4 and 6 nanoclusters, we find a continuous series of stable clusters. The former are predicted to disproportionate to the pure binary structures, which could be attributed to the competition between different structural types adopted by end members. The optical behavior of most stable clusters considered is contrary to the quantum confinement model.