I just rerun the Notebook attached to the original post with Mathematica 13.0.0. The behavior is the same: the number is steps required to find the minimum strongly depends on the scale of the residual vector: dividing the latter by 2 (!) results in 984 steps instead of 220 steps with the original vector, multiplying it by 10 decreases the number of steps to 51. Splitting minimization in two calls to FindMinimum reduces the number of steps to 120. Evaluation time is also nearly the same as with version 8.0.4 installed on the same machine.

No response from the Wolfram Team so far. It seems that the basic implementation does not have changed since version 8.