We report the results of a conjoint experimental/theoretical effort to assess the structures of free-standing zinc clusters with up to 73 atoms. Experiment provides photoemission spectra for Zn_N⁻ cluster anions, to be used as fingerprints in structural assessment, as well as mass spectra for both anion and cation clusters. Theory provides both a detailed description of a novel protocol to locate global minimum structures of clusters in an efficient and reliable way, and its specific application to neutral and charged zinc clusters. Our methodology is based on the well-known hybrid EP-DFT (empirical potential-density functional theory) approach, in which the approximate potential energy surface generated by an empirical Gupta potential is first sampled with unbiased basin hopping simulations, and then a selection of the isomers so identified is re-optimized at a first-principles DFT level. The novelty introduced in our paper is a simple but efficient new recipe to obtain the best possible EP parameters for a given cluster system, with which the first step of the EP-DFT method is to be performed. Our method is able to reproduce experimental measurements at an excellent level for most cluster sizes, implying its ability to locate the true global minimum structures; meanwhile, if exactly the same method is applied based on the existing Gupta potential (fitted to bulk properties), it leads to wrong predicted structures with energies between 1 and 2 eV above the correct ones. Opposite to what was claimed in the past, our work unequivocally demonstrates that Zn clusters are not amorphous, and they rather adopt high symmetry structures for most sizes. We show that Zn clusters have a number of exotic, unprecedented structural and electronic properties which are not expected for clusters of a metallic element, and describe them in detail.