Ola Raphael,
Acessa o live.com e digita o erro
dá uma olhada também na RFC 1035 para verificar se os teus MXs estao corretos de acordo com a norma.
Nao está te listando um link para tu analisar, geralmente estas mensagens dizem pq vc nao está conseguindo.