Since you don't know how they got in you are looking at a pretty ugly situation. First I would check to see if you are running any old scripts like an outdated version of PhpBB. Often those are ways your typical script kiddie gets in.
When you do find the hole, patch it and move on. If they were in there as root, then just pony up the money for an OS reinstall and put your backup on then fix the security leak.
-A
|