We discuss the availability questions that arise when digital time stamps are used for preserving the evidentiary value of electronic documents. We analyze the time-stamping protocols known to date and point out some weaknesses that have not been addressed so far in scientific literature. Without addressing and solving them, any advantage of the linkage-based protocols over the hash-and-sign time-stamping would be questionable. We present several new techniques and protocols for improving the availability of both the hash-and-sign and the linkage-based time-stamping services. We introduce fault-tolerant linking as a new concept to neutralize fault-sensitivity as the main weakness of linkage-based time-stamping.