Você não precisa ter uma conta de hotmail para usar o MSN Messenger. Eu não. O problema, no entanto, é que você precisa alterar o e-mail associado à sua conta.
Você pode ir ao live.com e fazer login. Lá, no lado direito, você verá seu nome de usuário. Mova o mouse sobre ele e a opção Conta será exibida. Lá, na parte inferior da página, você verá outras opções e, nessa área, "seus endereços de e-mail". Clique aqui e mude o endereço para outro endereço.
Isso deve permitir que você mude para um novo endereço e mantenha seus contatos do MSN sem nenhuma intervenção do lado deles (ou pelo menos isso aconteceu comigo há alguns anos).