The problem, as I see it, is not that there are magic items that give +X to some skill. The problem is that some DMs give out +X items too cheaply, to characters of too low level, and without regard to what skill the item is boosting. I wouldn't worry too much about your ring of ledgewalking, since Balance isn't as useful as, say, Tumble even at lower levels.
The cost (and hence, availability relative to level) of a +skill item should depend on how useful the skill is both in general and at the level of the character who would most likely have the item. At higher levels, when characters are more likely to have spells, items, and abilities allowing them to fly, change shape into winged creatures, or whatnot, Balance is pretty useless, while Spellcraft is more useful than ever given the increased number of enemies with spells or spell-like abilities. Skills that can be replaced with spells (such as Move Silently with silence, or Swim with polymorph self/polymorph other) should be cheaper than those cannot be so replaced (Spellcraft again).
The final thing that should be considered is the relative availability of the skill. Giving +X to Craft or Profession doesn't take anything away from any specific player character, since almost all classes have these as class skills. Giving +X to a skill like Read Lips or Use Magic Device, OTOH, will take away from the party's rogue.
I feel that trying to achieve general balance in +skill magic item creation will prove to be a "nicer" solution, as it will involve a lot less dice rolling (and stack better with other "roll twice" effects, like the granted power of the Luck domain).
