After some time I found that changing the "PEG Link Mode" from "Auto" (CMOS default, system shipped with it) to "Normal" or "Disabled" helped stability a lot. PEG stands for PCI-Express Graphics, so it would make sense that ASUS overtuned something in their BIOS. Nothing is known about what this option really does.
I have this motherboard(A8N32), and the PEG Link Mode option automatically overclocks the graphics cards, that is its only function. Which explains the instability.