Hi
One way to combat this, albeit at a cost to performance is to simply simulate it twice per frame.
This is possible in the current beta (i.e 4.1+). You can simply do something like this:
// Make the AI not do any movement by itself
ai.canMove = false;
// Run the movement code multiple times per frame
int timeMultiplier = Mathf.Round(Time.timeScale);
for (int i = 0; i < timeMultiplier; i++) {
Vector3 nextPosition;
Quaternion nextRotation;
ai.MovementUpdate(Time.deltaTime / timeMultiplier, out nextPosition, out nextRotation);
ai.FinalizeMovement(nextPosition, nextRotation);
}