From looking at your images, I would say that 2 coefficients should work. Using 3 coefficients does not always help. It adds an extra degree of freedom to the camera model, which may cause the optimization to become unstable.
The reason that rectification fails in this case, is that undistorting these images folds them upon themselves, and the function cannot determine the correct size of the output image. If you want to see what is happening, try exporting the stereoParameters object, and calling the rectifyStereoImages function with the 'OutputView' parameter set to 'full'.
