How to deal with insignificant work / wrong methodology in papers, when it is discussed correctly?
I haven't personally had similar experiences before, and probably am much more junior than you (only really have reviewed a relatively small number of papers at all still), but here's my thoughts (I am familiar with the specific case of Machine Learning though):


  I was a bit surprised to recieve a revision of the manuscript, where my remarks were just included in the discussion section: In fact they did not improve the experiment, but in the discussion they more or less stated "it is possible that everything we wrote in here is invalid due to the problem of overfitting".


Did they really only just add that in a discussion, or did they also adjust other places? Typically, a very short (e.g. one-sentence) summary of results is included in places like Abstract / Introduction / Conclusions, something like "our approach X performs well on problem Y". If there are any claims in any places like that, those would be unjustified in my opinion, and that would be a serious problem. There really shouldn't be any unjustified claims about performance anywhere in the paper.


  So in the end they had a paper with a good justification for the project, a maybe working method which was not applied correctly, and they interpreted the results correct - so all in all it was an well documented example for a failure, and it was formally correct.


If the intuition / ideas behind the proposed approach are sound / interesting and new, if it all sounds like it could work out and be interesting... I think there might be some value in publication. Of course this also depends on the venue, some have lower standards than others. I suppose I'd treat it as a paper that simply didn't have any empirical evaluation at all, try to decide whether or not you'd still accept it then?


  Still, my recommendation was to refuse the paper, but I was considering if it might be helpful to others because they could learn from the mistakes.


That's not what peer-reviewed papers are for. I do believe papers with "failures" in the sense of interesting ideas that, after a proper evaluation, turned out not to work should be valued more highly than they tend to be (only success stories that "beat state of the art" tend to be accepted). Such failures can provide useful insights when published, prevent others from coming up with the same ideas and wasting their time on them again. But accepting a paper with a methodological flaw so that others can use it as an example of what not to do in a paper? That doesn't seem valuable to me.