  We have conducted a search for new stars of high proper motion ($\geq$0.4
arcsec yr$^{-1}$) using POSS II fields for which an extra IIIaF (red) plate of
good quality exists, along with useable IIIaJ (blue) and IV-N (infrared) plates
taken at epochs differing by a minimum of 1.5 years. Thirty-five fields at
Galactic latitudes $|b| \geq$ 20$^o$ were measured, covering some 1378 deg$^2$,
or 3.3% of the sky. Searches with three plate combinations as well as all four
plates were also made. Seven new stars were found with $\mu \geq$0.5 arcsec
yr$^{-1}$, which were therefore missed in the Luyten Half Second (LHS) Catalog.
One of these is a common proper motion binary consisting of two subdwarf M
stars; another is a cool white dwarf with probable halo kinematics. As a test
of our completeness -- and of our ability to test that of Luyten -- 216 of 230
catalogued high proper motion stars were recovered by the software, or 94%.
Reasons for incompleteness of the LHS are discussed, such as the simple fact
that POSS II plates have deeper limiting magnitudes and greater overlap than
did POSS I. Nonetheless, our results suggest that the LHS is closer to 90%
complete than recent estimates in the literature (e.g 60%), and we propose a
reason to account for one such lower estimate. The conclusion that the LHS
Catalog is more complete has implications for the nature of the halo dark
matter. In particular it strengthens the constraint on the local density of
halo stars, especially white dwarfs at M$_V\sim$17-18.
