Different ssh fingerprints on server. (MITM attack?)

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)