A subset of microquasars exhibits high peculiar velocity with respect to the local standard of rest due to the kicks they receive when being born in supernovae. The interaction between the radio plasma released by microquasar jets from such high-velocity binaries with the interstellar medium must lead to the production of trails and bow shocks similar to what is observed in narrow-angle tailed radio galaxies and pulsar wind nebulae. We present a set of numerical simulations of this interaction that illuminate the long-term dynamical evolution and the observational properties of these microquasar bow-shock nebulae and trails. We find that this interaction always produces a structure that consists of a bow shock, a trailing neck, and an expanding bubble. Using our simulations to model emission, we predict that the shock surrounding the bubble and the neck should be visible in Hα emission, the interior of the bubble should be visible in synchrotron radio emission, and only the bow shock is likely to be detectable in X-ray emission. We construct an analytic model for the evolution of the neck and bubble shape and compare this model with observations of the X-ray binary SAX J1712.6-3739.