when you find a trojan the best thing to do is fdisk or replace the mach as you did. if some one was in, you really have no idea what they might have done. Any 'fixs' are just guesswork.

if you don't have some kind of auditing enabled, you could be trying to figure out what they did for a long time. And the lock-outs might be an oversight as suggested, although that is highly suspicious.