Why not cluster one dimension at a time? K-means will meaningfully cluster for 2 of these dimensions and fail for the other 998. Measure how good the separation is and stick with the best X dimensions.
The curse of dimensionality appears here in the fact that the "number" of possible ways of projecting the space increases dramatically with the dimension.
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.