Mutualisms are ubiquitous, but models predict they should be susceptible to cheating. Resolving this paradox has become relevant to synthetic ecology: cooperative cross-feeding, a nutrient-exchange mutualism, has been proposed to stabilize microbial consortia. Previous attempts to understand how cross-feeders remain robust to non-producing cheaters have relied on complex behaviour (e.g. cheater punishment) or group selection. Using a stochastic spatial model, we demonstrate two novel mechanisms that can allow cross-feeders to outcompete cheaters, rather than just escape from them. Both mechanisms work through the spatial segregation of the resources, which prevents individual cheaters from acquiring the resources they need to reproduce. First, if microbe dispersal is low but resources are shared widely, then the cross-feeders self-organize into stable spatial patterns. Here the cross-feeders can build up where the resource they need is abundant, and send their resource to where their partner is, separating resources at regular intervals in space. Second, if dispersal is high but resource sharing is local, then random variation in population density creates small-scale variation in resource density, separating the resources from each other by chance. These results suggest that cross-feeding may be more robust than previously expected and offer strategies to engineer stable consortia.