Hi, ikalo
Yes, you are suggesting that the box needs to be secured, or it will happen again. This is very true, but we will need to know a lot more about how it happened to advise on that one. There are some good tutorials and hints and tips on this site already.
For example, if the attacker has physical access, then a physical solution will be required (don't wear your best silk shirt ;) )
Sure, I agree entirely that the reformat re-install route is very tedious, but I did state that it was the "textbook" answer.
The real problem is that we do not know enough of the circumstances to give much more than general advice?...................if it is just room-mates at college messing around, it is a bit different from someone in an online gaming clan (those guys can get really intense?)
I think that we have to accept a back-door as being almost inevitable in these circumstances?
In the end, the re-format and re-install may be the quickest and easiest route.............it is certainly the most secure.
Cheers
