Sure, a tagged oxygen atom is likely to survive 2000 years I think, and would most likely be found still on Earth, in a place of highest oxygen density, which is probably any liquid water anywhere. Altitude has little to do with it since water isn't particularly more dense under pressure.

Not so much a science question as a statistics one. It is more likely to be in a cubic meter of water than a cubic meter of anything else on Earth except for perhaps laboratory liquid oxygen.

The molecule is more likely to be in a place of higher oxygen density than not (per given volume) but every oxygen molecule has an equal chance of being the particular molecule you're after regardless of location (all things being equal). Say you are looking for a cat and you know there are four cats in your house and one outside somewhere in the neighborhood. You'd look in your house first because it's easier, but no one cat in your house has any greater likelihood of being the cat you want than the one outside.

If every atom of oxygen is equally likely to be drawn from a series of independent random draws, this implies that the probability of obtaining a particular oxygen atom within a volume of size V is proportional to V. So picking bigger volumes to search in makes it more likely to contain the elusive oxygen atom you're after.

However, this doesn't say anything about the speed of the strategy. If the rate oxygen atoms can be individually processed does not vary with the volume you're searching in, then any search strategy that ensures non-repeats would be optimal (IE there's no search strategy preferences).

If you can process all the oxygen atoms within a considered volume at once, then obviously you choose the biggest volume you can (and get the oxygen atom immediately).

Search strategies depending on the volume size would be a continuum between 'it doesn't matter which you pick' and 'the biggest volume', and would depend on the specifics of the method you are using to test which oxygen atom is which.

This isn't really philosophy, it's an exercise in probability.