Does gridsearch on random forest/extra trees make sense? I have seen many posts online about tuning the random forest hyperparameters with a gridsearch. however, since the random forest creates trees with some randomness, does this have sense? Wouldn't the best parameters just be because of a lucky model?
Let me make an example. I tuned the parameters of an ExtraTreeClassifier, getting very nice results. However, training with the same parameters changing the random state (seed) of the model leads to terrible performance. Am I allowed to think that the model trained works well?

To add a little to @Björn's answer, when the model selection criterion is noisy (or there is a random element to the classifier) grid search (or random search) actually makes more sense than some more elegant or more efficient model selection procedures, such as gradient descent or Nelder-Mead simplex, where the randomness may affect the termination criterion for the optimisation algorithm (they generally stop when the improvement in performance or the "gradient" is small).
Randomness in the construction of a classifier is not ideal, so minimising it by e.g. using lots of trees is a good idea.  One problem is that the noisyness of the classifier construction may make it easier to over-fit the model selection criteria if the "randomness" of a particular classifier just happens to suit the sampling variation in the validation set (or cross-validation) error.
