Thank you guys for all your input. It is now clear that replacing the PSU solved the problems. Nice timing since the old PSU decided to croak just when I did the first replacements, but still. I ended up with a completely new build, which was desired, just not so fast 
