We present results from a campaign of multiple epoch echelle spectroscopy of relatively faint (V = 9.5-13.5 mag) red giants observed as potential astrometric grid stars for the Space Interferometry Mission (SIM PlanetQuest). Data are analyzed for 775 stars selected from the Grid Giant Star Survey spanning a wide range of effective temperatures (Teff), gravities and metallicities. The spectra are used to determine these stellar parameters and to monitor radial velocity (RV) variability at the 100 m/s level. The degree of RV variation measured for 489 stars observed two or more times is explored as a function of the inferred stellar parameters. The percentage of radial velocity unstable stars is found to be very high -- about 2/3 of our sample. It is found that the fraction of RV-stable red giants (at the 100 m/s level) is higher among stars with Teff \sim 4500 K, corresponding to the calibration-independent range of infrared colors 0.59 < (J-K_s)_0 < 0.73. A higher percentage of RV-stable stars is found if the additional constraints of surface gravity and metallicity ranges 2.3< log g < 3.2 and -0.5 < [Fe/H] < -0.1, respectively, are applied. Selection of stars based on only photometric values of effective temperature (4300 K < Teff < 4700 K) is a simple and effective way to increase the fraction of RV-stable stars. The optimal selection of RV-stable stars, especially in the case when the Washington photometry is unavailable, can rely effectively on 2MASS colors constraint 0.59 < (J-K_s)_0 < 0.73. These results have important ramifications for the use of giant stars as astrometric references for the SIM PlanetQuest.