Nem entre em pânico, você sabe que o mestre da cocada preta aqui está com a solução, e de fato é simples, acesse os links:
http://postmaster.live.com/FAQ.aspx
http://www.microsoft.com/mscorp/safe…d/default.mspx
Se após ajustes de SPF e MX perfeitamente configurados o serviço de email não enviar corretamente para hotmail, yahoo ou uol, veja isto aqui:
http://help.yahoo.com/help/us/mail/defer/defer-06.html
Nada de pânico, negócio é ver se há blacklist de spam, veja: