What is the best (hopefully free or cheap) way to detect and then, if necessary, remove a rootkit found on your machine?
SysInternals stopped updating RootKit Revealer a couple of years ago.
The only sure way to detect a rootkit is to do an offline compare of installed files and filesystem metadata from a trusted list of known files and their parameters. Obviously, you need to trust the machine you are running the comparison from.
In most situations, using a boot cdrom to run a virus scanner does the trick, for most people.
Otherwise, you can start with a fresh install of whatever, boot it from cdrom, attach an external drive, run a perl script to find and gather parameters (size, md5, sha1), then store the parameters.
To check, run a perl script to find and gather parameters, then compare them to the stored ones.
Also, you'd need a perl script to update your stored parameters after a system update.
--Edit-- Updating this to reflect available techniques. If you get a copy of any bootable rescue cd (such as trinity or rescuecd) with an up-to-date copy of the program "chntpasswd", you'll be able to browse and edit the windows registry offline.
Coupled with a copy of the startup list from castlecops.com, you should be able to track down the most common run points for the most common rootkits. And always keep track of your driver files and what the good versions are too.
With that level of control, your biggest problem will be the mess of spaghetti your registry is left in after you delete the rootkit and trojans. Usually.
-- Edit -- and there are windows tools, too. But I described the tools I'm familiar with, and which are free and better documented.
Remember that you can never trust a compromised machine. You may think you found all signs of a rootkit, but the attacker may have created backdoors in other places. Non-standard backdoors that tools you use won't detect. As a rule you should reinstall a compromised machine from scratch.