If the cable isn't frayed, it sounds like a kink in the cable near a cable stop, i.e. it becomes stiff when the kink tries to enter a section of housing. With Shimano rear derailleurs, it doesn't take much to screw up the shifting : the derailleur's spring is often too weak IMHO, and the slightest imperfection with the cable routing or the housing causes problems. Often when I redo a derailleur line, shifting works perfectly for a while, then starts missing shifts once in a while at the first rain shower, and it goes down from there. That's how sensitive it is.
If I were you, I'd buy high quality teflon coated housing and cable, and I'd redo the entire line myself. Unless you know the LBS very well, he probably won't do it juuuust right the way you want it. When you redo the cabling, cut the sections of housing so they make nice "natural" curves between the stops, with the cable entering and leaving the stops tangential to the housing whenever possible. Also, cut the housing with a quality tool and make sure you dremel the ends of the housing flat with the housing arched like it will be when installed. After you prepare an end, don't forget to open up the hole with a ballpoint pen or something, so nothing rubs. Also try to use metal ferrules instead of plastic ones. Then when you slide the cable in the new housing, watch for any sudden stiffness, which would indicate a kink in the housing. The idea of all this is to eliminate friction and slop as much as possible, so the shifting is light and crisp.
If you keep having problems, you can try a Rollamajig (http://www.mtbr.com/reviews/Extras/product_20952.shtml
), and if you're still not satisfied and you're a bit of a perfectionist, replacing the derailleur's return spring with a stronger one usually solves the problem once and for all, although it's a real PITA, and you need to know how to make springs if you can't find the perfect replacement.