Though, isn't it possible for malware and such to "live through" a factory restore?
No. (If it's done right.)
Then we must not have been doing it right in the past.
Then again, I think what we couldn't get rid of was roguewear. (Though all the malicious things, like viruses, keyloggers, roguewear etc... Are categorized as malware, yes?)
Well, it sounds like refurbished is the way to go. I'm sure the manufacturers would restore a computer "correctly", right? I guess I'm just malware-paranoid haha.