We present radial velocity measurements of a sample of M5V-M9V stars from our Red-Optical Planet Survey, operating at 0.652-1.025 mu m. Radial velocities for 15 stars, with rms precision down to 2.5 m s(-1) over a week-long time-scale, are achieved using thorium-argon reference spectra. We are sensitive to planets with m(p)sin i >= 1.5 M-circle plus (3 M-circle plus at 2 Sigma) in the classical habitable zone, and our observations currently rule out planets with m(p)sin i > 0.5 M-J at 0.03 au for all our targets. A total of 9 of the 15 targets exhibit rms 10 M-circle plus in 0.03 au orbits. Since the mean rotation velocity is of the order of 8 km s(-1) for an M6V star and 15 km s(-1) for M9V, we avoid observing only slow rotators that would introduce a bias towards low axial inclination (i < 90 degrees) systems, which are unfavourable for planet detection. Our targets with the highest v sin i values exhibit radial velocities significantly above the photon-noise-limited precision, even after accounting for v sin i. We have therefore monitored stellar activity via chromospheric emission from the H alpha and Ca ii infrared triplet lines. A clear trend of log(10)(L-H alpha/L-bol) with radial velocity rms is seen, implying that significant starspot activity is responsible for the observed radial velocity precision floor. The implication that most late M dwarfs are significantly spotted, and hence exhibit time varying line distortions, indicates that observations to detect orbiting planets need strategies to reliably mitigate against the effects of activity-induced radial velocity variations.