Does associative recognition retrieve target when given re-paired foil?
What is being described in the original question is called Recall-to-Reject Processing. In "Associative recognition: a case of recall-to-reject processing" by Rotello and Heit provides evidence this retrieval of an older memory for comparison with the newer probe, rather than retrieving nothing, does indeed happen.

To show this, they ran three experiments. Experiment 1 dealt with word pairs similarly to the experiment cited in the original post. Experiment 2 test on both word pairs and individual pairs.

The results of Experiment 1 show accuracy was higher for newer pairs than for re-arranged pairs. Consequently, one can infer that Recall-to-Reject had a harder time with re-arranged pairs due to interference [1]. The same occurred in Experiment 2, but additionally showing interference with words similar to those studied.

They summarize the result in their conclusion:


  [Recall-to-Reject Processing] makes a distinctive prediction about the ability of subjects to discriminate completely new test stimuli from stimuli that are new but similar to studied materials. Specifically, the similar test foils should be increasingly rejected, relative to a baseline of completely new items, late in processing (i.e., after information from the recall component of recognition becomes available). The data from Experiments 1 and 2 are consistent with that prediction: We did find that rearranged pairs were increasingly rejected, relative to new pairs, after about 1,000 msec.


However, it should be noted this is quite an old paper and an updated reference would be helpful.

[1] There's also some sort of trend happening with lags, but this isn't really necessary to understand for this answer.