A combinatorial approach is employed to investigate the atomic and electronic structures of a metal vacancy in titanium carbide. It turns out that the usual relaxed geometry of the vacancy is just a metastable state representing a local energy minimum. Using ab initio calculations and by systematically searching through the configurational space of a Ti monovacancy, we identify a multitude of local minima with reconstructed geometry that are lower in energy. Among them, there is a planar configuration with two displaced carbons forming a dimer inside the vacancy. This structure has the optimal number and order of C-C bonds making it the global minimum. Further calculations show that this reconstructed geometry is also the ground state of metal vacancies in other carbides such as ZrC, HfC, and VC. The reconstructed metal vacancies are characterized by localized electron states due to the relatively short C-C bonds. The defect states lie just below the upper and lower valence bands. The existence of reconstructed vacancy configurations is essential for understanding the mechanism of metal self-diffusion in transition-metal carbides.