We have conducted a novel search of most of the southern sky for nearby red dwarfs having low proper motions, with specific emphasis on those with {mu}<0.18"/yr, the lower cutoff of Luyten's classic proper-motion catalog. We used a tightly constrained search of the SuperCOSMOS database and a suite of photometric distance relations for photographic BRI and 2MASS JHK_s_ magnitudes to estimate distances to more than 14 million red dwarf candidates. Here we discuss 29 stars in 26 systems estimated to be within 25 pc, all of which have {mu}<0.18"/yr, that we have investigated using milliarcsecond astrometry, VRI photometry, and low-resolution spectroscopy. In total, we present the first parallaxes of 20 star systems, 9 of which are within 25 pc. We have additionally identified 14 young M dwarfs, of which 3 are new members of the nearby young moving groups, and 72 new giants, including two new carbon stars. We also present the entire catalog of 1215 sources we have identified by this means.