telnet localhost 22
Trying 127.0.0.1...
Connected to localhost.
Escape character is '^]'.
SSH-2.0-SSH-1.99-OpenSSH_3.5p1


service sshd status 
As you can see it doesn't give sshd but this crazy characters, in both cases

1628 ?        S      0:02 ?a?@°Ó?@?
22871 ?        S      0:00 ?a?@°Ó?@?

ls -l /usr/sbin/sshd
-rwxr-xr-x    1 root     root      3963123 sep 16 00:03 /usr/sbin/sshd

md5sum /usr/sbin/sshd
1624e238c7d82ffcca3731534a06e9e8  /usr/sbin/sshd

They are trying to get in all the time
Sinds I changed root password and disabled remote root login, he is still trying to login as root and whatever password

Last night after trying to login, cups is started. Is this normal?

Sep 21 02:59:24 itact     [13797]: LoginGraceTime exceeded.
Sep 21 02:59:57 itact     [13866]: LoginGraceTime exceeded.
Sep 21 03:01:18 itact     [14043]: LoginGraceTime exceeded.
Sep 21 03:01:42 itact     [14093]: LoginGraceTime exceeded.
Sep 21 03:02:44 itact     [14228]: LoginGraceTime exceeded.
Sep 21 03:03:10 itact     [14287]: LoginGraceTime exceeded.
sep 21 04:02:05 itact cups: cupsd afgesloten succeeded
Sep 21 04:02:06 itact modprobe: modprobe: Can't locate module char-major-188
Sep 21 04:02:07 itact last message repeated 15 times
sep 21 04:02:07 itact cups: cupsd start op succeeded