People kept noticing that blood donors were healthier than non-donors. Could giving blood be good for you, perhaps by removing excess iron? Perhaps medieval doctors practicing blood-letting were onto something? Running some studies (1998, 2001) this does seem to be a real correlation, so you see articles like "Men Who Donate Blood May Reduce Risk Of Heart Disease."
While this sounds good, and it's nice when helpful things turn out to be healthy, the evidence is not very strong. When you notice A and B happen together it may be that A causes B, B causes A, or some hidden C causes A and B. We may have good reasons to believe A might cause B, but it's very hard to rule out a potential C. Instead if you intentionally manipulate A and observe what happens to B then you can actually see how much of an effect A has on B.
For example, people observed (2003) that infants fed soy-based formula were more likely to develop peanut allergies. So they recommended that "limiting soy milk or formula in the first 2 years of life may reduce sensitization." Here A is soy formula, B is peanut allergy, and we do see a correlation. When intentionally varying A (2008, n=620), however, B stays constant, which kind of sinks the whole theory. A likely candidate for a third cause, C, was a general predisposition to allergies: those infants were more likely to react to cows-milk formula and so be given soy-based ones, and they were also more likely to react to peanuts.
To take another example, based on studies (2000, 2008, 2010) finding a higher miscarriage rate among coffee drinkers pregnant women are advised to cut back their caffeine consumption. But a randomized controlled trial (2007, n=1207) found people randomly assigned to drink regular or decaf coffee were equally likely to have miscarriages. [EDIT: jimrandomh points out that I misread the study and it didn't actually show this. Instead it was too small a study to detect an effect on miscarriage rates.] A potential third cause (2012) here is that lack of morning sickness is associated with miscarriage (2010) and when you're nauseated you're less likely to drink a morning coffee. This doesn't tell us the root of the problem (why would feeling less sick go along with miscarriages?) but it does tell us cutting back on caffeine is probably not helpful.
Which brings us back to blood donation. What if instead of blood donation making you healthy, healthier people are more likely to donate blood? There's substantial screening involved in becoming a blood donor, plus all sorts of cultural and economic factors that could lead to people choosing to donate blood or not, and those might also be associated with health outcomes. This was noted as a potential problem in 2011 but it's hard to test this with a full experiment because assigning people to give blood or not is difficult, you have to wait a long time, and the apparent size of the effect is small.
One approach that can work in places like this is to look for a "natural experiment," some way in which people might already be being divided into appropriate groups. A recent study (2013, n=12,357+50,889) took advantage of the situation where screening tests sometimes give false positives that disqualify people. These are nearly random, and give us a pool of people who are very similar to blood donors but don't quite make it to giving blood. When comparing the health of these disqualified donors to actual donors the health benefits vanish, supporting the "healthy donor hypothesis."
This isn't to say you should never pay attention to correlations. If your tongue starts peeling after eating lots of citric acid you should probably have less in the future, and the discovery (1950) that smoking causes lung cancer was based on an observation of correlations. Negative results are also helpful: if we don't find a correlation between hair color and musical ability then it's unlikely that one causes the other. Even in cases where correlational studies only provide weak evidence, however, they're so much easier than randomized controlled trials that we still should do them if only to find problems to look into more deeply with a more reliable method. But if you see a news report that comes down to "we observed people with bad outcome X had feature Y in common," it's probably not worth trying to avoid Y.
I also posted this on my blog.
I think it's way higher. Some off the top of my head (with a little reading to confirm details):
Child delivery by doctors in a hospital correlated with puerperal fever. Refined to a correlation between child delivery by someone who had recently performed an autopsy and puerperal fever. Experimentally testing handwashing (though not blind) confirmed effect, doctors wash their hands, dying in childbirth is now less common.
A student with anemia symptoms turns out to have some strangely shaped blood cells. This initial association is expanded by people looking at blood of other people with anemia, and several others also have these elongated red cells. Eventually we get enough of a correlation that we've discovered sickle cell anemia.
In fact I would go as far as to say that most of our medical knowledge comes from correlations, often relatively obvious ones like "getting run over by a car increases your chance of death".
There may still be something here, though: the kinds of studies we see with bad correlations being misleading, and the examples you give of successful ones, are generally small effects compared to the amount of time involved. Can we characterize better this area where correlations are especially suspect?
Epidemiological studies of diets (that is, health consequences of particular patterns of food intake) are all based on correlations and the great majority of them is junk.