Convergence now seems to work in all cases (as of cbb258e3b36dc2b497fa112c9803e28372025b5e ).
The issue was with calling the iterative solvers with the last strain increment as initial guess. This initial guess was apparently sometimes so bad, that the resulting residual vector's entries became disparate enough to cause significant precision loss