Consider the problem of estimating a linear time-invariant process across a communication channel such that the sensor data is delayed by a stochastically time-varying amount that can potentially be infinite. Thus, the data may arrive at the receiver delayed and out of order, or may simply be lost. There are two main contributions of this work. We show that the effect of the delay on the estimation error covariance cannot be characterized through a few moments of the delay distribution. Thus, intuitive conjectures such as a delay distribution with lesser mean, variance, or maximum value always yields better estimation performance are incorrect. For a graph with each edge introducing a random delay to the sensor data, we also provide a routing algorithm that searches for the path that is optimal from an estimation theoretic perspective. A minor contribution of the work is to obtain stability conditions when the delay distribution has an infinite support and delays are correlated across time.