Hi Eric,
I don't know right off if twisted pairs does much of anything for shielding low voltage wires. I know it cancels the field self induced by motor power wires, but that is the only place where I have heard that twisted pairs accomplish anything. But, you're the expert on that anyway.
You can maybe get ahold of cable with shielded pairs, too, all wrapped inside of a larger outer shield. But, I somehow doubt that encoder wires would crosstalk to each other anyway.
Can you swap encoders with another axis to find out if the problem follows?
Whatever is counting your encoder output is what I would suspect. Is that in your drive or in the computer?
First you get good, then you get fast. Then grouchiness sets in.
(Note: The opinions expressed in this post are my own and are not necessarily those of CNCzone and its management)