Depends on a game and overall design. I'm not going to say that there is a genre where it would never work (because someone would just prove me wrong with a single datapoint saying otherwise) but I'd say that
a) It must be very carefully balanced
b) Game should have better rewards for those who handle the greater challenge. That should solve the problem of "rewarding mediocrity".
Take shmups, for instance. The better the player plays in them, the harder they usually get. (at least most of the good ones.) However, the "better" playing is also tightly coupled with the mechanics of scoring, which is essentially the main rewarding system, which means that harder difficulty=higher scores. I actually like this type of system more than pre-set easy-normal-hard-very hard -steps, because first, they are by definition able (when executed right) to give the "right" difficulty for everyone, and second because it keeps everyone's scores on the same scale.
Of course, this type of system does not fit into every game. Also, if awards for good playing are items, completely losing opportunity to get some specialized gear because of good play would be mildly off-putting.