The energy costs of transferring data from sources in Wireless Sensor Networks (WSNs) to sinks at the edge of the network are high. These high costs have generated much interest in data storage strategies within the WSN. The frequently dangerous and power limited conditions in which nodes are required to operate can however result in the loss of nodes that are vital data storage points. We extend work on a reliability enhancing WSN data storage strategy called Address Coding that provides power efficient self organizing backup capability in networks of homogeneous nodes. We show that the asymptotic energy cost per backup is lower with Address Coding than it would be for a naive storage strategy based on AODV. We also show that probabilistic flooding can be applied to Address Coding, yielding significant reduction in energy cost with negligible loss in reliability.