Compromised computer, Recovery options

What to do if your computer/client/server/box/machine/pda has been
compromised.

Most likely you will have to reinstall everything from scratch.
If you have been compromised, you might not want to trust your
backups anymore, unless the backup was burned down on CD or
DVD media.

Here is a few important links to consider reading.

Live-CD Diagnostics
http://www-128.ibm.com/developerworks/linux/library/l-livecddiag/

CERT®/CC Steps for Recovering from a UNIX or NT System
Compromise:
http://www.cert.org/tech_tips/win-UNIX-system_compromise.html

Microsoft Says Recovery from Malware Becoming Impossible
Link

Help: I Got Hacked. Now What Do I Do? - Microsoft TechNet:
Security Management Column:
Security Management

Anti-Malware Engineering Team : News on Alcan, Mywife.E: