Security :: SSH Config - What's To Stop The MIM From Making A Substitution Of Keys During The Initial Exchange

Ive been running ssh to log into server for long time. Recently a x-win app reported that it suspects a man in the middle attack (MiMA), so I want to tighten this up, but it seems to me if there is a MiM, then the initial key exchange is vulnerable to a substitution. This is on solaris, but since its a basic concept I'm ot getting, it shouldnt matter,

Here's the gist of what I read:

- create users key pair,
- enable host authentication (ssh_config file on client and sshd_config file on remote host)
- start an ssh session and accept the remote hosts key (and I assume the remote host will take client users key and store some where)

Questions:

1. What's to stop the MIM from making a substitution of keys during the initial exchange?? Shouldn't the keys be initially transfered in a more secure fashion??

2. Does the server just accept new keys from any existing user who want to create an ssh session? So if some one knows a username and password (such as the owner of an application they know is running) couldn't they just create their own keypair and have the server accept them?