A small fraction of quasars have long been known to show bulk velocity offsets (of a few hundred to thousands of km/s) in the broad Balmer lines with respect to the systemic redshift of the host galaxy. Models to explain these offsets usually invoke broad-line region gas kinematics/asymmetry around single black holes (BHs), orbital motion of massive (~sub-parsec (sub-pc)) binary black holes (BBHs), or recoil BHs, but single-epoch spectra are unable to distinguish between these scenarios. The line-of-sight (LOS) radial velocity (RV) shifts from long-term spectroscopic monitoring can be used to test the BBH hypothesis. We have selected a sample of 399 quasars with kinematically offset broad H{beta} lines from the Sloan Digital Sky Survey (SDSS) Seventh Data Release quasar catalog, and have conducted second-epoch optical spectroscopy for 50 of them. Combined with the existing SDSS spectra, the new observations enable us to constrain the LOS RV shifts of broad H{beta} lines with a rest-frame baseline of a few years to nearly a decade. While previous work focused on objects with extreme velocity offset (>10^3^ km/s), we explore the parameter space with smaller (a few hundred km/s) yet significant offsets (99.7% confidence). Using cross-correlation analysis, we detect significant (99% confidence) radial accelerations in the broad H{beta} lines in 24 of the 50 objects, of ~10-200 km/s/yr with a median measurement uncertainty of ~10 km/s/yr, implying a high fraction of variability of the broad-line velocity on multi-year timescales. We suggest that 9 of the 24 detections are sub-pc BBH candidates, which show consistent velocity shifts independently measured from a second broad line (either H{alpha} or Mg II) without significant changes in the broad-line profiles. Combining the results on the general quasar population studied in Paper I (Shen et al. 2013ApJ...775...49S), we find a tentative anti-correlation between the velocity offset in the first-epoch spectrum and the average acceleration between two epochs, which could be explained by orbital phase modulation when the time separation between two epochs is a non-negligible fraction of the orbital period of the motion causing the line displacement. We discuss the implications of our results for the identification of sub-pc BBH candidates in offset-line quasars and for the constraints on their frequency and orbital parameters.