what about, similar to what puki suggested, creating a bank in the style of a 2 dimensional array similar to this:
Dim HaveICheckedThesePairs(MaxElementsList1,MaxElementsList2)
and prior to performing your collision check (or whatever you are hoping to do) check if the current pair have already been checked.
It will still mean you are looping through, at worst, the number of elements^2 but you at least only perform your 'collision check or other intensive routine once per pair.
Dim HaveICheckedThesePairs(MaxElementsList1,MaxElementsList2)
and prior to performing your collision check (or whatever you are hoping to do) check if the current pair have already been checked.
It will still mean you are looping through, at worst, the number of elements^2 but you at least only perform your 'collision check or other intensive routine once per pair.