Why leave-one-out cross validation fails to detect overfit? I have an extremely simple classification problem. My data-set looks like this:
| feature | target |
| A       | 1      |
| A       | 1      |
| B       | 0      |
| A       | 0      |
....................
| A       | 0      |
| B       | 0      |
| A       | 1      |

As you can see the feature cant take only two values (A and B) and the target is always either 0 or 1. My goal is to predict probability of target = 1 given a value of the feature.
I construct a data set such that probability of target = 1 does not depend on feature and is equal to 0.5. I have generated a data set in which feature is equal to A 1000 times and equal to B also 1000 times.
Just by chance for the feature = A 1 is observed 515 times out of 1000 and for the feature = B 1 is observed 482 times out of 1000.
I have two alternative models. The first one states that probability of target = 1 does not depend on values of the feature (this model is correct per construction). The second model states that probability of target = 1 depends on the value of the feature (this model is an overfit per construction).
Now assume that I run a standard leave-one-out cross validation to find out if the second model is an overfit or not. When I take one observation with feature = A out, the number of 1s for feature = A will fluctuate between 515 and 514 and, therefore, the predicted probability for A will be either 515 / 999 or 514 / 999, which is very close to in-sample probability (515 / 1000). So, the second model will be better than the first model not only in-sample but also out-of-sample (obtained via leave-one-out cross validation)!
So, it means that we were not able to detect an over-fit with the leave-one-out procedure and the second model, which has smaller predictive power, wins the first model, which has better predictive power.
Is it a known problem? How to deal with this? Is there a procedure that is free of errors like this?
I understand that one could run a test that checks if there is statistically significant difference between probability of 1 for different values of features but my question is about cross-validation and leave-one-out specifically. For more complex data we do not have a test, we run a cross-validation there and I want to be sure that for those more complex cases the cross-validation does not fool me like in the described simple case.

Your example is one of purely observation-driven modeling. And your observations indicate that there is a relationship between your feature and your target. Yes, it's a weak association. But that it is overfitting is not evident from the data you have observed! You can't very well accuse LOOCV of failing to detect overfitting that you only know is there because you know the true data generating process (DGP), i.e., you have information that is not available to the LOOCV method.
Also, "overfitting" is not a Boolean attribute. On the one hand, we never know the true DGP outside simulations, so we can never truly say there is overfitting: anything could conceivably have an influence on our outcome. On the other hand, if you believe in "tapering effect sizes", we will never be able to capture all influences, so we will always have underfitting.
Thus, it makes more sense to think of "overfitting" as a continuum. How much worse does adding a predictor make my model for future expected losses (which we again will only be able to estimate, unless we know the true DGP)? Thus, we have to think about how much signal there is in our data. In the present case, the overfitting is quite weak, and as Dikran says, it is hard to distinguish a weak effect from no effect whatsoever. And adding this feature will only have a very small effect on future predictions, so the overfitting, measured on a continuum, is small.
Per above, you are modeling purely based on the observations here. Essentially, such a model has no predilection towards a simpler model, like the one without an effect of the feature. There are various ways of including such a predilection. Essentially, we would bias our models towards simplicity, and per the bias-variance tradeoff, this may very well improve future predictions. In the terminology above, our overfitting, if present, would be weaker.

*

*We could explicitly run a Bayesian model with a prior on the impact of the feature.

*As you write, we could include elements of NHST, only accepting the more complex model if the improvement in fit is statistically significant.

*Or we would use the "one standard error rule", which is very often used in cross-validation.

