Global optimizations via a genetic algorithm using the Gupta empirical potential are performed on 34-atom Pd-Pt binary clusters, finding a complex crossover among several structural motifs that are close in energy. The composition range is then restricted on the basis of stability criteria; (a) the Gupta global minima at each composition are subjected to density functional (DFT) local energy minimizations, and (b) at the 24-10 composition, the lowest-energy isomers of each structural family are locally optimized at the DFT level. It is found that the energetic ordering of the structural motifs predicted by the Gupta potential is not confirmed at the DFT level and that a new structural motif, a mixed decahedral/close-packed (Dh-cp(DT)) one, is the putative global minimum at all compositions. Finally, segregation effects of Pd atoms to the surface of the cluster are studied at the composition Pd17Pt17 and found to be corroborated by DFT calculations. The peculiar stability of the Dh-cp(DT) arrangement is rationalized in terms of an optimal compromise between core-segregated, and thus preferentially close-packed, Pt atoms and surface-segregated, and thus preferentially decahedral, Pd atoms.