If you have root access to the server, the easy way to solve such problems is to run sshd in debug mode, by issuing something like /usr/sbin/sshd -d -p 2222 on the server (full path to sshd executable required, which sshd can help) and then connecting from the client with ssh -p 2222 user@host
To prevent irrelevant keys from being offered, you have to explicitly specify this in every host entry in the ~/.ssh/config (on the client machine) file by adding IdentitiesOnly like so:
Host www.somehost.com
IdentityFile ~/.ssh/key_for_somehost_rsa