Decidable restrictions of the Post Correspondence Problem
Ehrenfeucht, Karhumäki and Rozenberg have shown that binary PCP (where the domain is binary) is decidable. Halava and Holub later showed that it's actually in P.