(Apparently, while I was editing my post @nenik already said most of what I was going to post 
@Aponthis you may want to take a look at a motion planning library, for example, https://vexforum.com/t/qcc2-gyro-and-pid-control-code/29292/1
Your observations are correct: PID is only guaranteed to work around small linear region. Over the long distances, especially when PID values get saturated and you start clipping max power, it is no longer mathematically consistent. What you have in those cases is not a proper PID and textbook tuning methods are no longer applicable.
Here is a simple way to think about motion planning for starters:
Instead of targeting final encoder position, target robot velocity and left-right encoder diff over the long distances. You will still need a separate PID loop for each (maintaining desired velocity and encoders diff between left and right), but they will be much simpler to handle.
I thought I’ve seen recently a sample code posted by @tabor473, but I couldn’t find it for some reason.
As you get close to your target position you switch from velocity targeting to position PID to precisely stop.
Also, you would need to do some smoothing to get good velocity estimates, or your inputs will be noisy with round off errors and similar stuff.
The simplest way to try motion planning, even before you get up to speed with the library, would be to create a function that takes target position and desired velocity (values for which you determine experimentally).
Then inside that function you first start gradually increasing motor power using some fixed slew rate until you get close to the target velocity.
Then you start maintaining the desired velocity for a while using its own PID loop (with separately tuned coefficients) until you get into vicinity of the target position.
Once you close to the target position, you switch to the next step of regulating position (instead of velocity) with a next PID loop having its own coefficients.
When you arrive within some small error of the target position you exit from that function, ready to do the next step.
Try to code the above function first, mostly for educational purposes. The next step would be to add mini power corrections for driving straight to both velocity and position targeting segments. There were a number of threads that popped up on the forums regarding this topic lately, with some really good tips and tricks for doing that.
The goal of this exercise is to get to the point when you understand what the library is doing. At that point you could either integrate the whole library into your code or just include the relevant portions of the code.
Finally, to take precision driving to the next level, you would have to switch from the individual sensors used as feedback input to your PID loops, to the sensor fusion model.
In sensor fusion model you take input from all sensors at once and process through some math model, for example, using Kalman filter to estimate some parameters of the system like “true” position and velocity. The math behind the model does not necessarily 100% believes each individual sensor at each point of time. Instead, it believes each of them less than 100% and “averages” various sensors over short period of time thus improving overall accuracy by smoothing over noise in the individual input measurements.
I’ve seen a library from one of the VEXU teams (BNS?) posted a while ago. When I have time later today I will try to find those links and post them here, but if somebody else knows those links and could do that first, it would be great.
