Ok, I feel like an idiot. I gave up too quickly before trying everything that I had thought to try. After writing starting this forum thread, I discovered two other symptoms. First symptom was that on system power on, it took longer than normal to get to the POST screen and it made some clicking noises which I don't remember from before. It didn't sound anything like POST error code beeps so I did not know what to make of it. The 2nd symptom was that when booting up windows, the computer sometimes locks up before getting to the login screen.
So before I started the thread here, I had thought to re-seat the graphics card but I was sure that it was flush with the PCI Express connector and I thought to myself, "naaaa. That would be an ALL-OR-NOTHING kind of problem anyway".
So I decided to re-seat the graphics card this morning and now everything works as expected. All three tests I did above (WEI, 3dMark06, WOW) are now giving the results I expect to see. I have done a few cold boots since then and everything is still working. Problem solved.