I found a solution for this problem.
It is a problem with OCd cards. The Asus Matrix 580 I have is factory overclocked to 816 Mhz. Running at 816 "rewarded" me with 5-10 fps in all games. Going down to the default clock of a 580 (772 mhz) fixed this issue immidiately.
I have found out that I can go up as high as 799 on the core with good performance. 805 Mhz, for example, resulted in the old stuttering.