[EricH]

Does it behave this way when the encoders and/or the gyro are removed from the system, by code or other means? Mechanically, it should track pretty straight even without the sensors--at least, it should only go one way.

Are your speed controllers calibrated? It sounds like on one side, you're getting more power at half throttle, but the other gets more power at full--but I suspect that isn't the whole story.

Are there signs of wear, or debris, in one or both gearboxes? That might be jamming you up a little bit.