Power system frequency could be captured by digital recordings and extracted to compare with a reference database for forensic time-stamp verification. It is known as the electric network frequency (ENF) criterion, enabled by the properties of random fluctuation and intra-grid consistency. In essence, this is a task of matching a short random sequence within a long reference, and the reliability of this criterion is mainly concerned with whether this match could be unique and correct. In this paper, we comprehensively analyze the factors affecting the reliability of ENF matching, including length of test recording, length of reference, temporal resolution, and signal-to-noise ratio (SNR). For synthetic analysis, we incorporate the first-order autoregressive (AR) ENF model and propose an efficient time-frequency domain (TFD) noisy ENF synthesis method. Then, the reliability analysis schemes for both synthetic and real-world data are respectively proposed. Through a comprehensive study we reveal that while the SNR is an important external factor to determine whether time-stamp verification is viable, the length of test recording is the most important inherent factor, followed by the length of reference. However, the temporal resolution has little impact on the matching process.