Using the simplest meta-population model capable of informing vaccination policy, we have demonstrated that heterogeneity in vaccine coverage increases the population-immunity threshold (below which outbreaks will occur on the introduction of an infectious person), especially when sub-populations mix non-randomly. Insofar as children with religious or philosophical exemptions not only live in the same households or neighborhoods, or attend the same schools, but also associate preferentially with other children having like-minded parents, non-medical exemptions reduce our ability to prevent outbreaks of vaccine-preventable diseases disproportionately (i.e., more than randomly distributed and mixed susceptible people do). By virtue of higher reproduction numbers or lower vaccine efficacy, some diseases are closer to the random mixing threshold than others. Among measles, mumps and rubella, for example, mumps is closest, followed in turn by measles and rubella, and immunity to mumps may wane absent boosting. Travelers infected abroad who still harbor the pathogens responsible for these diseases on returning to the US may cause outbreaks where immunity is heterogeneous or mixing non-random. Thus, despite average two-dose coverage of the measles, mumps and rubella vaccine above 90%, the mumps outbreaks on residential college campuses in the rural mid-west during 2006 and 2009, and ongoing within an orthodox Jewish community in the northeast, might have been expected in retrospect.