We make a case that, even with severe efficiency constraints, taking the number of bits to code each motion vector into account when estimating motion for video compression results in significantly better performance at low bit rates, using simulation studies on established benchmark image sequences. In particular, we examine an algorithm that differs from a "vanilla" implementation of the H.261 standard by choosing motion vectors to minimize a cost function of prediction error and the number of bits to code a particular motion vector, where the coefficients of the cost function are adapted on-line using the Widrow-Hoff rule. We show that this algorithm performs comparably to a variety of more idealized, computationally intensive methods we examined in earlier papers and substantially better than the original vanilla" method, which ignores the number of bits to code the motion vector when choosing it.