You seem to be assuming that the models work in additive fashion, so adding a feature to the model just "adds" some stuff related to this feature alone and does not influence the rest of the model, same with removing the feature. That is not the case. If machine learning models worked like this, then to build a model with $k$ features you would need only to build $k$ models with single feature and find a way of combining them. Here you can find a recent thread, and links to many other questions like this, where including new feature to regression model affects how the model uses the other features. This happens for linear regression, but will also be true for other machine learning algorithms.
You say that you would assume this to be issue "only" when the variables are correlated, but with real-life data, there always will be some degree of correlation between the variables. Moreover, it is not only about correlations between pairs of variables, but also about relations between all of the variables, where those relations can be non-linear as well. You should be rather talking about independence, and seeing all variables independent is even less likely then seeing them all uncorrelated.
More then this, by adding a new feature your algorithm needs to adapt. Imagine that you have a decision tree with the constraint to have not more then five samples in each final node. You cannot just add new feature to such tree without re-building it, because you already have not more then five samples in each final node, so you cannot split this node any further. In such case, you would need to re-build the whole tree, using different splits, or combinations of splits, so it would use your data in a different way then the initial tree. This would be the case even if the new feature that you are adding is independent of other features.
What you propose is partially answered also in the Algorithms for automatic model selection thread, that discusses stepwise feature selection algorithms and the most upvoted answer shows how proceeding in such stepwise fashion by adding (or removing) variables leads to ending up with bad models. It simply doesn't work for the reasons discussed above.