As for market-paradigm shifts, I totally agree. One way to deal with that is to constantly re-optimize the parameters based on recent data. This is also known as walk-forward optimization on which there is a slide at the very end (see http://blog.quantopian.com/parameter-optimization/ for a more information).
Finally, as to running multiple strategies with different parameter settings. The OLMAR paper that describes the algorithm (http://arxiv.org/abs/1206.4626) has a variation of this where they use a range of different-length moving averages, rather than just one.
To anyone newly thinking about this topic, it is certainly the most challenging project you can take on. There are no laws of the market like there are laws of physics. You can get your code to work perfectly, but all that means is that your results will be the same as your model's going forward. As for a model, it's likely to need to change fairly frequently, even becoming the opposite of a previously great model for example, and you can never truly account for the effect of politics on markets. One tip is that a sudden catastrophic crash is far more likely than a gigantic surprise to the upside so if you're playing with real money, you need to use options to insure against such an event. Luckily (or not luckily in the case of trading itself) markets are highly correlated, so index options will probably fill this need.
If you actually want to trade moving average strategies, your best best is just to diversify and run several different strategies across a variety of parameter sets and across various sectors/asset classes, without trying to overly optimize a single strategy