Sascha: Interesting cut down of your post The reason I thought it might be the graphics card is because it is graphics corruption. I got the corruption, I hooked up the wife's laptop on VGA, it didn't have corruption, I skipped back to the DVI and got the corruption so I thought I could rule out the monitor. I also checked whether it was just the DVI by using the computer's VGA, but I still got the "incorrect resolution" message and so ruled out just the DVI.
The monitor was the next thing I was going to check tonight. Luckily we've got another computer in the house, so I'll check that first.
Xemanth: I had an Aspire laptop, so I'm guessing that isn't entirely relevant. Unless of course you managed to track down the cause to display or graphics card.
 From the looks of it I'll be shelling out about the same for a new monitor as I would for bottom of the range-ish replacement motherboard/processor/memory if it is the monitor that's going. Typical!
Looks like it is my monitor and not my graphics. Despite working with the laptop while the desktop showed corruption, the alternate monitor isn't showing the same symptoms.
I made it show the "not optimum resolution" message by restarting the machine, powered the machine down, swapped monitors and everything worked fine. Previously I've needed to wait for 15-30 minutes before it would work again, this took just a few minutes.
Now I just need to work out what is a decent replacement on my budget and find out whether some of the brands that I knew as main brands in the 90s (like Iiyama) and some of the big names (LG and Phillips) are actually any good.