TH - you mentioned you *never* trust tools on the suspected host... and I understand that if a rootkit was installed that it can intercept system calls and other processes so the application or tool running may return false results. What are your opinions of programs like Sysinternal's RootkitRevealer and F-Secures Blacklight?
I have mixed views of such tools. The differentiator being that the effectiveness is decided by the hands of the analyst they're put in.

That said, the kit has to be running before it can do anything. In most cases, a nice forensic CD is sufficient to handle the problem. SLueth comes to mind as well as Helix.

Of course I have to be special and have my own custom tools along with the ultimate in forensics - ENCASE.