This article describes a good basic strategy to take when you are forced by a security compromise to reinstall your servers. It hasn't happened to me in a couple of years, but Mathew Tanase struck a cord with me in "Starting from Scratch: Formatting and Reinstalling after a Security Incident" when he says:
There is a point you reach in the recovery process, after you have done a little digging, put a finger on what might have gone wrong, where you come to the proverbial "fork in the road". Every security professional or systems administrator has faced the decision at some point in his or her career: is it better to try to repair the damage, or just reinstall the system and start from scratch?