Turns out I did a Rookie-mistake. I was simply evaluating the residual wrong since I was not applying the boundary conditions. Therefore my residual was artifically high along the boundary. For the solution see this:
For reasonable small DOFs and reasonably small time discretization the standard solver, as well as the Krylov solver equipped with BiCGStab and hypre_amg as preconditioner, solves the coupled Navier-Stokes-Equation up to a precision of 1e-12.