Many high-income countries currently experience large outbreaks of vaccine-preventable diseases such as measles despite the availability of highly effective vaccines. This phenomenon lacks an explanation in countries where vaccination rates are rising on an already high level. Here, we build on the growing evidence that belief systems, rather than access to vaccines, are the primary barrier to vaccination in high-income countries, and show how a simple opinion formation process can lead to clusters of unvaccinated individuals, leading to a dramatic increase in disease outbreak probability. In particular, the effect of clustering on outbreak probabilities is strongest when the vaccination coverage is close to the level required to provide herd immunity under the assumption of random mixing. Our results based on computer simulations suggest that the current estimates of vaccination coverage necessary to avoid outbreaks of vaccine-preventable diseases might be too low.