Is cross-validation still valid when the sample size is small? I have what seems to be a very basic confusion about cross-validation.
Let us say I am building a linear binary classifier, and I want to use cross-validation to estimate the classification accuracy. Imagine now that my sample size $N$ is small, but the number $k$ of features is large. Even when features and classes are randomly generated (i.e. "actual" classification accuracy should be 50%), it can so happen that one of the features will perfectly predict the binary class. If $N$ is small and $k >> N$, such a situation is not unlikely. In this scenario I will get 100% classification accuracy with any amount of cross-validation folds, which obviously does not represent the actual power of my classifier, in a sense that probability to classify a new sample correctly is still only 50%. [Update: this is wrong. See my answer below for  the demonstration of why it is wrong.]
Are there any common methods of dealing with such a situation?
For example, if I want to assess statistical difference between my two classes, I could run MANOVA which in case of two groups reduces to computing Hotelling's T. Even if some of the features yield significant univariate differences ("false positives"), I should get an overall non-significant multivariate difference. However, I do not see anything in the cross-validation procedure that would account for such false positives ("false discriminants"?). What am I missing?
One thing that I can think of myself, would be to cross-validate over features, e.g. to select random subset of features (in addition to randomly selecting a test set) on each cross-validation fold. But I do not think such an approach is often (ever?) used.
Update: Section 7.10.3 of "The Elements of Statistical Learning" entitled "Does Cross-Validation Really Work?" asks exactly the same question and claims that such a situation can never arise (cross-validation accuracy will be 50%, not 100%). So far I am not convinced, I will run some simulations myself. [Update: they are right; see below.]
 A: I figured out what is going on: Hastie et al. were (of course) right, and my intuition was wrong. Here is the demonstration of my logic flaw.
Let's say we have 10 samples, first five are class 1 and last five are class 2. Let's generate 200 random features. Several of them are likely to predict the class perfectly, I made them bold on the following plot:

If we do the t-tests between classes using each of these three features, we get three significant p-values: 0.0047, 0.011, and 0.0039. These, of course, are false positives due to cherry-picking. If we do a Hotelling's test using all 200 features, we get a non-significant p=0.61, as expected.
Now let's try to cross-validate. I do 5-fold stratified cross-validation, holding out 1 sample from each class to classify. The classifier will be LDA on all 200 features. I repeat this procedure 100 times with different random features, and the mean number of correctly decoded classes I get is 4.9, i.e. chance level!
Well, LDA with 10 classes and 200 features overfits badly. Let's select only the features with perfect class separation on the training test in each cross-validation fold. The resulting mean accuracy is 5.1, still chance level. Why? Because it turns out that the number of features I am using on each fold is larger than the number of "perfect" features on the whole dataset. There are features that look perfect on the training set, but have zero predictive power on the test set. And they screw up the classification.
This is exactly the point that I did not appreciate before.
Finally, one can only use the features with perfect class separation on the whole dataset. Then the mean accuracy is 9.3, but this is cheating! Of course we are not allowed to use any knowledge about the whole dataset when doing cross-validation.
