  Gravitational wave emission by coalescing black holes (BHs) kicks the remnant
BH with a typical velocity of hundreds of km/s. This velocity is sufficiently
large to remove the remnant BH from a low-mass galaxy but is below the escape
velocity from the Milky Way (MW) galaxy. If central BHs were common in the
galactic building blocks that merged to make the MW, then numerous BHs that
were kicked out of low-mass galaxies should be freely floating in the MW halo
today. We use a large statistical sample of possible merger tree histories for
the MW to estimate the expected number of recoiled BH remnants present in the
MW halo today. We find that hundreds of BHs should remain bound to the MW halo
after leaving their parent low-mass galaxies. Each BH carries a compact cluster
of old stars that populated the core of its original host galaxy. Using the
time-dependent Fokker-Planck equation, we find that present-day clusters are ~<
1 pc in size, and their central bright regions should be unresolved in most
existing sky surveys. These compact systems are distinguishable from globular
clusters by their internal (Keplerian) velocity dispersion greater than one
hundred km/s and their high mass-to-light ratio owing to the central BH. An
observational discovery of this relic population of star clusters in the MW
halo, would constrain the formation history of the MW and the dynamics of BH
mergers in the early Universe. A similar population should exist around other
galaxies, and may potentially be detectable in M31 and M33.
