I'll try replace the front cable. Funnily enough, I ordered a replacement cable and casing last time I had the indexing problem but assumed it had been resolved with a barrel adjustment. The outer sheath that it came with the cable isn't identical to the one on my bike, so I'll try lube up the new cable and stick it through the old outer sheath.
What can I do to free up the mech, aside from thorough cleaning and lubing? I did that 2 weeks ago.
I think putting the new cable in an old outer isn't worth it. Typically the outer has a plastic liner, then the steel strands then the plastic cover. The liner can wear causing all kinds of shifting grief. (As an aside, make sure you have gear cable outers, not brake cable outers. Gear cable outer is parallel strands, brake cable is spiral wrapped. Brake cable outer will screw up the indexing no end).
Does the mech move freely with the cable disconnected? Push it across against the spring by hand and release. Does it ping back? If it does, it's free enough already.