In an ad hoc mobile network, mobile users travel at variable velocity. The measurement of the motion velocity of a mobile user may not be consecutive due to possible missing observations. This paper presents an approach to the total cost estimation of variable velocity mobile location management for ad hoc mobile networks with missing measurements. Since the change of a mobile��s velocity within a short time period is limited due to physical restrictions, a mobile user��s future velocity is likely to be correlated with its past and current velocity. We propose to use the Gauss�CMarkov mobility model to capture the correlation of a mobile��s velocities. A Kalman filter of a linear uncertain discrete stochastic system is designed to estimate the total cost, and the formulas for calculating the steady state covariance of the estimation error of total cost are presented. A numerical example is given to illustrate the use of the proposed approach.