I'm actually troubleshooting an almost identical problem on my mom's computer right now. It too is experiencing odd video corruption on cold booting, but resetting or warm rebooting clears it up if it's been on for a couple minutes. I've also experienced other random weirdness like being unable to modify certain registry settings and being unable to click the "OK" button in my disk defragmenter.
I've eliminated (by swapping in known good parts) the power supply and memory and ran a thorough scan of the system hard drive that revealed no problems. I'm down to the video card, motherboard, and CPU - none of which have been altered in any way recently. (The only thing my mom said happened of late was accidentally hitting the power switch on the power strip - turning it on and off rapidly a couple times.)
The other thing to note is the dust was insane inside the case. I vacuumed as much out as I could, but still see a bunch underneath the heatsink fan in between the heatsink metal ribs. It sounds like the video card may be the culprit from other replies, but could a bad, failing, or damaged (due to heat) CPU cause something similar to what I reported? Is the motherboard also a possible cause of display corruption? Thanks for any feedback.