Are we past the point of repeatedly buying the same skill as you level, to get Fire Bolt II, Fire Bolt III, …, Fire Bolt CXVI? Just scale the skills with levels. I understand that having ten versions of each skill gives the illusion of “something new every level,” but you can give rewards that do not mess with your game’s scaling. You can even use a point investment mechanic to get most of the same effect without the annoyance of re-training and adjusting the hotbar.
City of Heroes does this. The Lord of the Rings Online™ does this (except for passive skills). Warhammer Online does this. Dungeon and Dragons, the basis for all these CRPG mechanics, has been doing this for decades (fireball does 1d6 damage per caster level, capped at 10d6), although not so much in 4th Edition.
Really, we promise to pretend not to notice that our spells do 5% more damage while we are fighting goblins with 5% more hit points. MMO players are used to looking past that. Just stop pretending that Fire Bolt III was a good design decision, and especially do not start calling them Lesser Fire Bolt, Fire Bolt, Improved Fire Bolt, Greater Fire Bolt, Lesser Fire Blast, Fire Blast, …, Supreme Exalted Fire Conflagration… And double-especially do not do that while having all those fire bolts on an alphabetized skill screen with no indication of level order.