1) You might have not uncovered everything, and its best not to take the risk. Format the drive and start from scratch. In the end it may save you time.
2) Isolate this server. Firewall it, put it on an isolated segment, or if it must be on the net, put it on a DMZ. Do not put it back where it was, with the old address - you have to make it as difficult as possible. Retire the old IP, or better yet create a honeypot there.
3) Disable as JD suggests remote access for any admin function including installation of applications. Make it difficult.
4) Ensure physical security - is the server room locked? Is entry to the room logged?
5) Do NOT have any shared logons to the system, especially ones with admin access. Every amdin user must have a unique ID with a password that must change on a regular basis and have strong password rules - 8 charecters, upper and lower case, numbers and special charecters. You may feel the need to have one "secret" login with a password that doesn't change in case you have a lockout feature.If you have one, do not use that login regularly (so it doesn't show up in a log), keep its existence quiet and make sure it has a very complex password.
6) Have a lockout feature that after X tries the account is disabled.
Am I paranoid?
Not at all. One company I worked for had their PBX hacked and had people logging on to make free long distance. Another had their website hacked and defaced.
James