A mechanic should have the same amount of utility to a 1st level character as to a 20th character. “Amount of utility” here means access to effects which are proportionate to one’s level.
On the other hand, don’t completely remove the roll of the dice from the effect. Keep in mind that the element of chance is always at play in D&D, so reward players who get lucky just like those who have high skills!
This consideration also comes into play when deciding whether to make the effects of a new rule scale with level or have a flat number attached to them. At some point, flat-number effects which begin as useful or challenging become either useless to perform or trivial to achieve. If instead scaled to high levels, they are initially impossible or pointless to attempt. This can frustrate the players if they depended on the effect, but on the other hand, effects which scale with them can remove the sense of progression and reward from the game.
My personal preference is the have the core of the mechanic scale with the players, but have side-mechanics which are flat. This way, the players see their characters progress from struggling to succeeding – in places where it is more cosmetic than not. Their bulk of their actual progression and levelling is then balanced mechanically by your chosen sliding scale.