Yes that will work. But, there are 1000C2 such combinations (that is, O(2^n)), and you have to try them all since you don't know which two dimensions are needed. And you cannot do each of the 100 separately in one-dimension and later hope to "combine" them together. In fact, you might not even know that it is 2 of the dimensions that are special. Maybe it is 7. So you have to try each of the 2^100 combinations separately. The algorithm you propose is not polynomial in the number of features.
I may be misunderstanding you, but the number of ways to pick 2 out of n dimensions is Θ(n²).
Even if we looked at up to d dimensions, (bruteforceable at Θ(n^d)), that doesn't imply we need to generalize to do all 1000.
The post you replied to actually suggested clustering just one dimension at a time. I think that's a reasonable solution given the situation you posited, where you have some dimensions that do cluster well, even individually, and some who are mostly noise.
I would say that the curse of dimensionality is more fundamental than the problem you describe. The problem doesn't lie just in separating noise from signal - in a truly high-dimensional space there may not be a "right angle" to see it from.
For a simple example, you may take randomly distributed points. Even at uniform random distribution, it is relatively easy to for instance index two dimensional points in such a way that you can later locate points that are close to any particular spot. For 20-dimensional points, this is very hard.
