Background: Continued belief in the 15-year old finding that ‘only 30% to 80% of all known published randomized trials were identifiable using MEDLINE’ (Cochrane Handbook chapter 6.1.1.2) may cause authors to accept sub-optimal MEDLINE recall uncritically. Objectives: To demonstrate a procedure to validate searches prior to their re-use in updating. Methods: Agency for Healthcare Research and Quality Evidence Reports and the original versions of updated Cochrane reviews from an existing cohort were eligible if they used a comprehensive search strategy and reported the MEDLINE search in enough detail to permit replication. One author replicated each search and another verified it. All included studies from the original reviews were tested to see if they had been indexed in MEDLINE at the time of the original search, and whether the search would have retrieved them. The authors’ own search was used to demonstrate the method. Results: Six updated Cochrane reviews and ten Evidence Reports met the eligibility criteria. Overall, recall of MEDLINE-indexed material was 0.50 in the original Cochrane reviews and 0.64 in Evidence Reports. In two of the six Cochrane reviews, the search strategy used in the update was different than the one used in the original review. One modification improved recall of the original targets from 0.50 to 0.67; the other reduced recall from 0.42 to nil. Capture-recapture analysis of the Cochrane reviews suggested that, despite poor MEDLINE retrieval, no studies were missing from the reviews. Conclusion: Efficiency of evidence discovery can be improved by validating the performance of the MEDLINE search against the MEDLINE-indexed evidence found through any means. If necessary, the search should modified for improved recall and peer reviewed before being used in the update.