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?

You are right that randomness will play a role (like with many other algorithms including MCMC samplers for Bayesian models, XGBoost, LightGBM, neural networks etc.) in the results. The obvious way to minimize randomness in the results of any hyper-parameter optimization method for RF (whether it's random grid-search, grid search or some Bayesian hyperparameter optimization method) is to increase the number of trees (which reduces the randomness in the model behavior - albeit at the cost of an increased training time). Alternatively, you construct a surrogate model on top of the results that takes into account that the signal, of where the best model in the hyperparameter landscape is, is noisy through an appropriate amount of smoothing/regularization.
