Applying Hold-out and CV technique
You are correct in the sense that when tuning your model via. grid search you are technically not leaking any data. But, recall that tuning your model (via. a specific procedure such as grid search) is one of only many steps you probably took in fitting your model pipeline. In particular, areas such as pre-processing, feature engineering, imputation, model tuning, data aggregations, etc. The point of the test set is to capture the entire model building process and not just the process of model tuning.

Furthermore, it is highly known that validation scores reported during model tuning tend to be optimistically biased (and this bias tends to be worse with smaller datasets). This is because the probability of finding a set of hyper parameters that coincidentally minimizes the error for the validation set but not to the overall population (i.e., overfitting to the validation set) becomes higher the finer your grid is. Imagine theoretically tuning your model to one million different hyper parameter combinations. The probability of selecting a bogus set of hyper parameters (i.e. that are only optimal for the validation set) is now quite large due to the sheer number of possible candidates you have elected to try.

With a test set, this still won't prevent overfitting to a validation set. However, it will allow you to detect the problem and give you the true unbiased measure of model performance.


  At the same time, it feels kind of strange, since with using both CV and Hold-out, I am guaranteed to get some outliers in the hold-out set (TEST in my text above), which will fail.


Indeed, which is a major drawback of cross validation and data splitting especially for smaller datasets (with a lot of outliers/noise). Basically, the performance measure you observe tends to be highly variable with how you split the data in the first place (that is, the seed you choose when splitting your data can lead to large changes in estimated model performance depending on where your outliers fall). The solution is unfortunately, not very glamorous and time consuming. In order to gain more certainty in our estimate, we need more than just a single estimate of model performance. Thus, simply repeat the entire model building process again with a different data partition (a different test set). Repeat this however many times, and average over all repeats. Possibly, form a confidence interval that allows you to see for yourself how variable your model's performance is.

I will also note that there are other ways to get around this problem, such as "optimism adjusted bootstrap", but recent issues have arisen with this method which have potentially shown that for high dimensional data this method does not do well, despite being more efficient than cross validation. Since high dimensional data is the norm these days, I have my doubts but perhaps it may be of use to you.