We analyze via theoretical approaches and molecular dynamics simulations the collective mode structure of strongly coupled two-dimensional binary Yukawa systems, for selected density, mass, and charge ratios, both in the liquid and crystalline solid phases. Theoretically, the liquid phase is described through the quasilocalized charge approximation (QLCA) approach, while in the crystalline phase we study the centered honeycomb and the staggered rectangular crystal structures through the standard harmonic phonon approximation. We identify "longitudinal" and "transverse" acoustic and optic modes and find that the longitudinal acoustic mode evolves from its weakly coupled counterpart in a discontinuous nonperturbative fashion. The low-frequency acoustic excitations are governed by the oscillation frequency of the average atom, while the high-frequency optic excitation frequencies are related to the Einstein frequencies of the systems.