Different ssh fingerprints on server. (MITM attack?)

Question

When I try to ssh to my server in Germany from my UK laptop I get:

IT IS POSSIBLE THAT SOMEONE IS DOING SOMETHING NASTY!
Someone could be eavesdropping on you right now (man-in-the-middle attack)!
It is also possible that a host key has just been changed.
.....

I removed the appropriate line from my ~/.ssh/known_hosts and then ssh'ed once again. On the server (via ssh terminal) I execute:

ssh-keygen -lf /etc/ssh/ssh_host_rsa_key.pub

then from my laptop I do:

ssh-keyscan -p 22 -t rsa my_domain_or_ip.com > /tmp/ssh_host_rsa_key.pub
ssh-keygen -l -f /tmp/ssh_host_rsa_key.pub

When I copare the results i see that the fingerprints are different! The length of the certificate is also different (on the server it is 2048 but remote scan shows 1024). The DSA fingerprints are also different.

The problem lies probably not in my local network, since arping for the server ip returns 0 results. I asked a friend in Poland to execute the same commands for me and he got the same results.

Any ideas on what is happening?

EDIT: When I ssh to the server and do:

ssh-keyscan -p 22 -t rsa 127.0.0.1 > /tmp/ssh_localhost_rsa_key.pub
ssh-keygen -l -f /tmp/ssh_localhost_rsa_key.pub

then I see that the fingerprint is still different! Then when I do on the server:

argping -c 5 server_ip

I get 0 responses.

This is very weird!

EDIT 2 (SUMMARY):

username@server:~$ ssh-keyscan -p 22 127.0.0.1 > /tmp/rsa.tmp
# 127.0.0.1 SSH-1.99-OpenSSH_33.33
username@server:~$ ssh-keygen -lf /tmp/rsa.tmp 
1024 12:.................................    127.0.0.1 (RSA)
username@server:~$ ssh-keygen -lf /etc/ssh/ssh_host_rsa_key.pub 
2048 32:................................. /etc/ssh/ssh_host_rsa_key.pub (RSA)

Answer 1

The cached key change can be explained by several reasons:

1. You were really attacked by someone who is sitting between you and your server and intercepting your sessions.
2. Your server IP is mapped to several real servers and you are recent switched to another machine. This can happen when you SSH to a VIP that can be switched between two servers.
3. Your server system has been re-installed recently which changed the SSH key.

You should be able to determine whether this is normal or not.

Answer 2

The problem was that somebody attacked my server with an exploit on one or more of the services that it runs. The solution was to reinstall the whole system unfortunately (I was afraid that somebody might have left some backdoors).

I also followed the linux security tips this time.