Does a statistically significant difference necessarily imply that prediction (via cross-validation) is possible? Example: if I find a statistically significant difference between the heights of men and women, does this say something about being able to predict whether a person is a man or woman based on the height?
It seems to me that in every case where there is a statistically significant difference, we should be able to make a prediction (classify something, and evaluate it using cross-validation) of the independent variable based on knowing the dependent variable. I couldn't think of a counterexample after a long period of thinking about it.
Another example: there is a linear correlation between $A$ and $B$. Given $B$, I would be able to predict $A$ with high certainty.
 A: Yes, you could. But there are easier ways to distinguish men from women. Assume that you find a significant difference of 4 inches between men and women, with respective average heights of 5'9" and 5'5". Then a sensible decision rule would be to assume maleness to anyone 5'7" or over. This is basically the approach taken by discriminant analysis.
But the big question is: how often do I make a mistake by this method?
The answer to that depends on the variances of the height distributions, which in your example, allow for a considerable overlap between the two populations and a big probability of false classification.
Recall that your hypothesized "significant difference" assumes that you took a sample of male and female heights. Given a real difference and a sufficiently large sample size, you will get a significant result. Basically, significance depends on the distribution of the sample averages; classification success depends on the distribution of the individual. So you can have a statistically significant result, but a totally crappy classifier.
