A new frontier in the search for dark matter (DM) is based on the idea of detecting the decoherence caused by DM scattering against a mesoscopic superposition of normal matter. Such superpositions are uniquely sensitive to very small momentum transfers from new particles and forces, especially DM with a mass below 100 MeV. Here we investigate what sorts of dark sectors are inaccessible with existing methods but would induce noticeable decoherence in the next generation of matter interferometers. We show that very soft, but medium range (0.1 nm - 1 $mu$m) elastic interactions between nuclei and DM are particularly suitable. We construct toy models for such interactions, discuss existing constraints, and delineate the expected sensitivity of forthcoming experiments. The first hints of DM in these devices would appear as small variations in the anomalous decoherence rate with a period of one sidereal day. This is a generic signature of interstellar sources of decoherence, clearly distinguishing it from terrestrial backgrounds. The OTIMA experiment under development in Vienna will begin to probe Earth-thermalizing DM once sidereal variations in the background decoherence rate are pushed below one part in a hundred for superposed 5-nm gold nanoparticles. The proposals by Bateman et al. and Geraci et al. could be similarly sensitive, although they would require at least a month of data taking. DM that is absorbed or elastically reflected by the Earth, and so avoids a greenhouse density enhancement, would not be detectable by those three experiments. On the other hand, the aggressive proposals of the MAQRO collaboration and Pino et al. would immediately open up many orders of magnitude in DM mass, interaction range, and coupling strength, regardless of how DM behaves in bulk matter.