The detection of frame deletion forgery is of great significance in the field of video forensics. Existing approaches, however, are not applicable to video sequences with variable motion strengths. In addition, the impact of interfering frames has not been considered in these approaches. Our research aims to develop a motion-adaptive forensic method as well as to eliminate interfering frames. Through a study of the statistical characteristics of the most common interfering frames such as relocated I-frames, we develop a new fluctuation feature based on frame motion residuals to identify frame deletion points (FDPs). The fluctuation feature is further enhanced by an intra-prediction elimination procedure so that it can be adapted to sequences with various motion levels. The enhanced feature is measured using a moving window detector to identify the location of a FDP. Finally, a postprocessing procedure is proposed to eliminate the minor interferences of sudden lighting change, focus vibration, and frame jitter. Our experimental results demonstrate that for videos with variable motion strengths and different interfering frames, the true positive rate of the algorithm can reach 90% when the false alarm rate is 0.3%. Our proposed method could provide a foundation for many practical applications of video forensics.