I must be missing something here, but why aren't you just storing all the properties for each element in memory, rather than querying the DB each time? Assuming you can allow 100MB of memory for this, and you have 70K elements, that's 1462 bytes per element, which should cover all your property needs. If it doesn't, allocate and/or buy more memory. This is by far the biggest time sinkhole right here.

Secondly, you should be able to generate the lowest "property pair" values by comparing your largest values with your smallest values, rather than doing a random selection. If you still want random output, exclude all pairs that will result in a value over your threshold (let's say you want 7, and item 1 has a value of 4, so anything with a value under 3 can be ignored), then choose from the resulting pool of pairs.

Anything else will just be polishing the finish.