Cross validation (applied solely for validation/verification purposes) avoids the double use of cases being in the training set and in the test set for the same model. However, performance estimates that are used to select the apparently best of a variety of models are in fact part of model training. So cross validation used for model selection or optimization is part of the training and then a separate test using data that is unknown to the whole training process (including model selection) is needed.
The reason for this is that the cross validation results are only estimates (or measurements) of model performance: they are subject to bias and variance, i.e. systematic and random errors.
because the sample may not be representative, the methods above may over/under-estimate the true model performance,
That's another way of saying, there's variance on the performance estimate in addition to possible bias. This is true for any kind of performance measurement (estimate based on testing cases): the test sample (whether held back by cross validation or obtained in any other way) may accidentally contain more easy cases or more difficult cases. So you'll have to expect some variance when testing the same model with different test sets. In resampling validation (including cross validation) you have an additional source of variance: you are actually testing surrogate models that are assumed to be sufficiently similar to the model trained on the whole data (for which the performance estimate is used) to be considered equivalent for practical purposes. However, if your training procedure is not stable, you'll see variance among the surrogate models, which will also add to the variance of your cross validation estimate.
So we end up with an almost unbiased but somewhat noisy estimate of performance ...
and so we will tend to choose those who perform better under the selected data,
So yes, when picking the apparently best performing model, we'll "skim off the noise", i.e. models that accidentally look good with the cross validation split we did will be favored.
The risk of skimming variance (= overfitting, selecting the wrong model) increases with
- increasing number of compared models
- increasing variance uncertainty on the performance estimates, and
- decreasing true difference in performance among the considered models
(although one may argue that this is less of a problem as the mistake here is only to select a not totally perfect model from a number of almost equally good models)
but not for out-of-sample data?
While the out-of-sample test set will may accidentally contain more easy cases than the population, it is unlikely that we're (un*)lucky here as well.
Side note: this may happen of course. But we can estimate the likelihood/extent of such random (bad) luck with the usual tools to estimate uncertainty on our point estimate.
My impression, however, is that in practice overoptimistic assessment of models more frequently happens due to biased sampling, such as cases being excluded for which no labels can be obtained (possibly because they are hard/borderline cases).
* I consider it bad luck if a model appears better than it actually is as I've had to deal a lot with data where unwarranted overoptimism may lead to harm.