I encourage customers to architect machines such that data is stored in a separate partition of the hard disk – this makes it far less painful should the worst case scenario of machine rebuild be required. It’s certainly true that insidious malicious software often takes advantage of cloaking (rootkit) techniques and once present are very difficult to remove – a machine rebuild is often the only way to be sure.
IMHO we need to take a different tack – Rootkits are best avoided as even the most elegant removal approach is painful. Encouraging (forcefully if necessary) users to operate their systems with MINIMAL privilege for day to day activities results in systems that are almost impervious to the scourge of rootkits, spyware, worms and viruses. No additional software or hardware is required to operate systems on a least privilege basis. There are excellent online resources detailing how to operate systems with least privilege including Aaron Margosis’ Non-Admin blog. Aaron's "table of contents" post is a good place to start.
I've blogged a great deal about the importance of and ways to make it easier to run without privilege.