The evolution of cross-feeding among individuals of the same species can help generate genetic and phenotypic diversity even in completely homogeneous environments. Cross-feeding Escherichia coli strains, where one strain feeds on a carbon source excreted by another strain, rapidly emerge during experimental evolution in a chemically minimal environment containing glucose as the sole carbon source. Genome-scale metabolic modeling predicts that cross-feeding of 58 carbon sources can emerge in the same environment, but only cross-feeding of acetate and glycerol has been experimentally observed. Here we use metabolic modeling to ask whether acetate and glycerol cross-feeding are especially likely to evolve, perhaps because they require less metabolic change, and thus perhaps also less genetic change than other cross-feeding interactions. However, this is not the case. The minimally required metabolic changes required for acetate and glycerol cross feeding affect dozens of chemical reactions, multiple biochemical pathways, as well as multiple operons or regulons. The complexity of these changes is consistent with experimental observations, where cross-feeding strains harbor multiple mutations. The required metabolic changes are also no less complex than those observed for multiple other of the 56 cross feeding interactions we study. We discuss possible reasons why only two cross-feeding interactions have been discovered during experimental evolution and argue that multiple new cross-feeding interactions may await discovery.