@Daniel, I think you are on the right track. However I am by no means an expert on this.
My take is that data mining can easily result in overfitting. And when that happens the optimization is unlikely to be useful on out of sample data (e.g. a time period outside of your optimization). And you won't notice if you test on the same time period.
In other words if you optimize and test on the same time period then during the testing you have a "time travel problem". This is because your optimization used data from the future relative to the "current date" within the backtest. This is also known as "look ahead bias".
To find a cure for this problem we must slay two issues: overfitting and time travel.
For overfitting I believe the answer is to use simple models (linear models are good) to reduce the chance of curve fitting. And don't spend a lot of time tweaking. Even better let your algorithm find "natural" ratios instead of putting in magic numbers. So an algorithm that responds to a 200 day trailing window is better than an algorithm based on "optimization" of years of historical data.
For time travel (aka look ahead bias) you should always validate your algorithm on previously unseen time periods. This includes all tinkering and development you did to choose your algo and tweaks you made to it. For instance you could do all of your testing on 2009-2010 time periods (hopefully randomizing within that) and then validate on 2011-2012.
If you have been developing on all time periods (2002-2013) and build a great "optimized" algo then you will have no choice but to start live paper trading to validate it. That is because the only "unseen" time period is strictly the future. (That is the great secret of "walk forward" testing since you are guaranteed to get unseen data). The downside is that your validation test will take days or weeks!