Re: I keep hearing about backups in the comments
Part of the issue in the cleanup will be what can you trust? How long were you really rooted
This is why you segregate data from OS.
It's a simple enough matter to rebuild servers with the automated deployment system you keep offline and powered down except for such difficulties. The passwords will be a little stale, but that;s not the end of the world. At that point, you have a blank server that will do what is needed.
All you then need do is to apply the relevant data - which, being non-executable, doesn't complain any root exploits.
This doesn't fix any directory services you might have running - they're probably toast, and need to be rebuilt from whatever you can find - although it appears that both OpenLDAP and Active Directory can both export to XML, so your backup could help there, even if it does require manual inspection before restore.
But what you really need is a management structure that gives a flying fuck about DR. And they're remarkably thin on the ground.
 I use Cobbler and Puppet for this sort of thing, but there are many options.
 Many a time and oft I've been called in to fix massive data loss. Invariably, someone on-site has bitched about proper backup in the past, but been ignored because it's not a problem management had encountered before, so they don't believe it will happen to them...
 There are a number of people in the area purporting to do the same as I do, but for sigificantly less money. I get called in - often by my competitors - once they've failed.