How should I handle a paper with incorrect experimental results? We found that a paper, published in an important CS conference, presents incorrect results in its experimental evaluation section.

Merely reading the paper is not sufficient to spot these mistakes, as the source of incorrectness lies within the the experimental evaluation and none of the algorithms/pseudo-code presented in the paper seems to be affected by it. That somehow explains how the error made it past the peer-review barrier.

We are currently in the process of circumscribing to what extent the results are incorrect. This is made difficult by the fact that the authors did not provide sufficient information to fully reproduce/verify their original experiment (not even upon gentle request), so we can only verify a limited portion of it (although it is substantial enough to draw our conclusions).

We tend to believe that the authors made a mistake in good faith and that they failed to spot it because they did not double-check the correctness of the results they obtained. We also don't have any reason to believe that the unreproducible portion of their results is incorrect as well.

We want to stress the fact that this problem only affects a subset of their results. The mistake they did somehow invalidates some of the conclusions of the experimental evaluation, although it does not seem to affect it as a whole nor to hinder the perceived worthiness of the algorithms presented in the paper.

We would like to ask what would be the best approach for disclosing this 'finding'. 

It would seem the first, and most sensible step, is that to inform the authors about the issue. Then what? What should we expect them to do? Are there any other options?
In my opinion, the right thing to do is to publish a paper to clarify what could have been wrong in the previous work. This adds to the knowledge and invalidating previous results/beliefs is part of the science. 

It is a good practice to inform the authors of your findings if you want to make sure as you said: 


  We also don't have any reason to believe that the unreproducible
  portion of their results is incorrect as well


By informing the authors, they might provide you with more information that might invalidate your conclusions.  

Assume good faith and accept that humans do mistakes.