Hi, maybe a legitimate user account combined with a local root exploit have been used to crack the server. Does this server has any legitimate user accounts? Are you sure you trust this users? Are you sure they (or you) don't write their passwords on a piece of paper?
Who has local access to the server (unprotected LILO/Grub, booting from CDROM (KNOPPIX), mount the hd on another system)? Even if it might be manipulated, you should check the uptime of the system.