Sim, o Windows Live pode ser uma dor. Verifique:
- Você não está em uma lista negra
- Seu servidor tem MX e registros DNS reversos
- Você tem registros DNS SPF (muitos servidores rejeitam o email sem um SPF válido, GMail por exemplo, aqui está uma explicação e um assistente )
- A resposta HELO do seu servidor de e-mail corresponde ao seu nome de host
- Seu servidor de e-mail não é um retransmissor aberto
- O seu registros de DNS 'TTL não é muito baixo - 86400 (24 horas) é recomendado (alguns spammers definem seu TTL muito baixo para atualizar regularmente os registros DNS forjados)