Safety-critical navigation applications require that estimation errors be reliably quantified and bounded. This can be challenging for linear dynamic systems if the process noise or measurement errors have uncertain time correlation. In many systems (e.g., in satellite-based or inertial navigation systems), there are sources of time-correlated sensor errors that can be well modeled using Gauss-Markov processes (GMP). However, uncertainty in the GMP parameters, particularly in the correlation time constant, can cause misleading error estimation. In this paper, we develop new time-correlated models that ensure tight upper bounds on the estimation error variance, assuming that the actual error is a stationary GMP with a time constant that is only known to reside within an interval. We first use frequency-domain analysis to derive a stationary GMP model both in continuous and discrete time domain, which outperforms models previously described in the literature. Then, we achieve an even tighter estimation error bound using a non-stationary GMP model, for which we determine the minimum initial variance that guarantees bounding conditions. In both cases, the model can easily be implemented in a linear estimator like a Kalman filter.