The time-dependent healing of frictional strength, whose underlying mechanism may vary, is often logarithmic with time, after a certain time duration called the cutoff time. We theoretically show that the cutoff time depends on the initial strength at the beginning of quasi-stationary contact. This comes from the fact that the healing rate depends negatively and exponentially on the current strength. If healing starts with the minimum strength attained instantaneously upon the application of normal load, "intrinsic" cutoff time t cx, which reflects the reaction rate constant of the underlying physico-chemical process, will be observed. In general, the observed cutoff time is the sum of t cx and the effective contact time t ini of asperities at the beginning of the healing. Hence, in slide-hold-slide (SHS) experiments, where t ini is inversely proportional to the slip velocity V prior in the sliding preceding the hold, two regimes are predicted. For high V prior (t ini $ll$ t cx), the observed cutoff time is independent of V prior, being ~t cx. For low V prior (t ini $gg$ t cx), the observed cutoff time is "apparent," being ~t ini inversely proportional to V prior. Both regimes have been identified in laboratory data. Incorporation of the present cutoff time theory into the rate and state evolution laws predicts that the velocity dependence of steady state will diminish at high velocities where effective contact time is $ll$ t cx. Furthermore, the two regimes for SHS tests are divided by this cutoff velocity. This also has been confirmed with laboratory data. Implications on the very long cutoff time observed for natural repeating earthquakes are discussed.