We investigate the expected space velocities and misalignment angles of the eccentric binary pulsars for a range of possible progenitor systems and natal kick models. In particular, the effect of the orbital separation at the instant of supernova is discussed. The results of our simulations, combined with recent proper-motion and misalignment angle measurements, lead us to conclude that, although the known systems generally provide evidence for asymmetric supernovae, none of the proposed natal kick velocity distributions are adequate. Instead, we find that while kicks are required to explain the space velocities of J0045-7319 and B1259-63, a slow kick velocity distribution with σ = 0 km s -1 and μ = 50 km s-1 predicts space velocities that demonstrate the best agreement with observation. The expected misalignment angle distributions for B1534+12, J0045-7319, and B1259-63 favor larger kicks but do not preclude a slow kick velocity distribution. Such a model is, however, inconsistent with the large kicks usually invoked to explain the velocities of single pulsars. We discuss possible means to reconcile the space velocities of eccentric binary pulsars and the velocity distribution of the pulsar population. These include constraining the progenitor systems of binary pulsars to preclude tight post-common-envelope systems and erroneous pulsar velocity measurements due to an inaccurate distance model.