Hybrid density functionals show great promise for chemically accurate first-principles calculations, but their high computational cost limits their application in nontrivial studies, such as exploration of reaction pathways of adsorbents on periodic surfaces. One factor responsible for their increased cost is the dense Brillouin-zone sampling necessary to accurately resolve an integrable singularity in the exact exchange energy. We analyze this singularity within an intuitive formalism based on Wannier-function localization and analytically prove Wigner-Seitz truncation to be the ideal method for regularizing the Coulomb potential in the exchange kernel. We show that this method is limited only by Brillouin-zone discretization errors in the Kohn-Sham orbitals, and hence converges the exchange energy exponentially with the number of k points used to sample the Brillouin zone for all but zero-temperature metallic systems. To facilitate the implementation of this method, we develop a general construction for the plane-wave Coulomb kernel truncated on the Wigner-Seitz cell in one, two, or three lattice directions. We compare several regularization methods for the exchange kernel in a variety of real systems including low-symmetry crystals and low-dimensional materials. We find that our Wigner-Seitz truncation systematically yields the best k-point convergence for the exchange energy of all these systems and delivers an accuracy to hybrid functionals comparable to semilocal and screened-exchange functionals at identical k-point sets. © 2013 American Physical Society.