If you lose code execution on your server to an attacker, you're done. 100% fucked. Everything in your environment needs to get stripped down and rebuilt from trusted sources. Do not be one of those people who rationalizes "oh, I just lost uid=4294967294". Gawker lost root. So will you.
It's possible that sometime not too far in the future that advice might need to be upgraded to "If you lose root, unplug and destroy the hardware and install a completely new machine from trusted sources".
(Why yes, I _did_ have that problem weighing on my mind while I investigated several machines that had a weekends worth of exposure to the recent Exim remote root exploit...)
