We report the results of a photometric search for giant stars associated with the cores of four high-velocity clouds (HVCs)-two of which are compact HVCs-using the Las Campanas du Pont 2.5 m and Cerro Tololo Blanco 4 m telescopes in combination with a system of filters (Washington M, T2+DDO51) useful for identifying low surface gravity, evolved stars. Identical observations of nearby control fields provide a measure of the ``giant star'' background. Our data reach M0=22 for three of the HVCs and M0=21.25 for the fourth, depths that allow the detection of any giant stars within 600 kpc. Although we identify a number of faint late-type giant star candidates, we find neither a coherent red giant branch structure nor a clear excess of giant candidate counts in any HVC. This indicates that the giant candidates are probably not related to the HVCs and are more likely to be either random Milky Way giant stars or one of several classes of potential survey contaminants. Echelle spectroscopy of the brightest giant candidates in one HVC and its control field reveals radial velocities representative of the canonical Galactic stellar populations. In addition to these null results, no evidence of any young HVC stellar populations (represented by blue main-sequence stars) is found, a result consistent with previous searches. Our methodology, specifically designed to find faint diffuse stellar populations, places the tightest upper limit yet on the total stellar mass of HVCs of a few times 105 Msolar.