Check out this article from the excellent SysInternals site on how legitimate companies like Sony install rootkits on your PCs.
When you look at all the effort Mark spent to diagnose and remove the problem, it's no wonder why so many PCs are infected and can't be fixed. There are rootkits that attach themselves to your MBR (master boot record), so even wiping the drive won't make them go away. Hopefully Vista will prevent this sort of abuse from going on, even from companies like Sony.
A book on Windows Rootkits.