Will cross validation performance be an accurate indication for predicting the true performance on an independent data set?
First off, a pragmatic answer: don't discount the possibility that the test set comes from a somewhat different distribution than the data set you're using for training and cross-validation.  You might think that shouldn't happen, but in practice it does seem to occur.

That said, let's go with your hypothetical and assume that the test set comes from exactly the same distribution as the rest of your data.  In that case, it is possible for cross-validation to lead you astray about which model is better, if you're using cross-validation to select hyper-parameters.

You can use cross-validation to either (a) select hyper-parameters, or (b) estimate the accuracy of your model -- but not both at the same time.

It appears you're using cross-validation to select the optimal hyper-parameters: you try many different choices for the hyper-parameters, for each choice estimate accuracy of that choice using cross-validation, and select the best choice.  When you do that, there's no guarantee that the resulting accuracy (with the best parameter) will be predictive of performance on the test set -- it might be an overestimate (due to overfitting).  If it's more of an overestimate for M1 than M2, then you might see what you saw.

If you want to both select hyper-parameters and estimate accuracy, I suggest that you have a separate held-out validation set for estimating accuracy, or use nested cross-validation.  See https://stats.stackexchange.com/q/65128/2921 and http://scikit-learn.org/stable/auto_examples/model_selection/plot_nested_cross_validation_iris.html.