So, I'm surprised I didn't know about this little gem of software until today.
Sysinternals has a wonderful piece of software called "RootkitRevealer" which shows "oddities" in the registry and filesystem, indicating a possible hidden rootkit.
Unfortunately, it appears to only support Windows XP/2003.
If anyone knows of similar software which supports Linux/Mac/Vista/7/etc, I'd be very interested to hear about it. Always looking for new resources for my bag of tricks!