The crust of accreting neutron stars plays a central role in many different observational phenomena. In these stars, heavy elements produced by H-He burning in the rapid proton capture (rp-) process continually freeze to form new crust. In this paper, we explore the expected composition of the solid phase. We first demonstrate using molecular dynamics that two distinct types of chemical separation occur, depending on the composition of the rp-process ashes. We then calculate phase diagrams for three-component mixtures and use them to determine the allowed crust compositions. We show that, for the large range of atomic numbers produced in the rp-process ($Z$∼10--50), the solid that forms has only a small number of available compositions. We conclude that accreting neutron star crusts should be polycrystalline, with domains of distinct composition. Our results motivate further work on the size of the compositional domains, and have implications for crust physics and accreting neutron star phenomenology.