We present a new puzzle involving Galactic microwave emission and attempt to resolve it. On one hand, a cross-correlation analysis of the Wisconsin Hα Mapper map with the Tenerife 10 and 15 GHz maps shows that the well-known DIRBE correlated microwave emission cannot be dominated by free-free emission. On the other hand, recent high-resolution observations in the 8-10 GHz range with the Green Bank 140 foot telescope by Finkbeiner et al. failed to find the corresponding 8 σ signal that would be expected in the simplest spinning-dust models. So what physical mechanism is causing this ubiquitous dust-correlated emission? We argue for a model predicting that spinning dust is the culprit after all, but that the corresponding small grains are well correlated with the larger grains seen at 100 μm only on large angular scales. In support of this grain-segregation model, we find that the best spinning-dust template involves higher frequency maps in the range 12-60 μm, in which emission from transiently heated small grains is important. Upcoming cosmic microwave background experiments such as ground-based interferometers, the Microwave Anisotropy Probe, and the Planck low-frequency interferometer with high resolution at low frequencies should allow a definitive test of this model.