The structure of metal clusters on MgO(001) is searched for by different computational methods. For sizes N < or = 200, a global optimization basin-hopping algorithm is employed, whereas for larger sizes the most significant structural motifs are compared at magic sizes. This paper is focused on Pt and Pd/MgO(001), which present a non-negligible mismatch between the nearest-neighbor distance in the metal and the oxygen-oxygen distance in the substrate. For both metals, a transition from the cube-on-cube (001) epitaxy to the (111) epitaxy is found. The results of our simulations are compared to experimental data, to results found for Au and Ag in the previous paper (paper I), and to predictions derived from the Wulff-Kaischew construction.