We had exactly the same problem and have tried a lot of things. But recently we have solved it. You need to set SPF and register it with hotmail. It should solve your issue.