We investigate a class of randomized peer-to-peer (P2P) approach to Internet-wide distributed data storage systems that promises to reduce the coordination complexity and increases performance scalability. The core of these randomized P2P data storage systems is the data replenishment mechanism. The data replenishment automates the process of maintaining a sufficient level of data redundancy to ensure the availability of data in presence of peer departures and failures. The dynamics of peers entering and leaving the network is modeled as a stochastic process. A novel analytical time-backward technique is proposed to bound the expected time for a piece of data to remain in P2P systems. Both theoretical and simulation results are in agreement, indicating that a proposed data replenishment via random linear network coding (RLNC) outperforms other strategies that employ popular repetition and channel coding techniques. Specifically, we show that the expected time for a piece of data to remain in a P2P system, the longer the better, is exponential in the redundancy amount for the RLNC-based strategy, while they are quadratic for other strategies.