I had a similar problem and setting up a valid reverse DNS records for all servers, the SPF record and DKIM solved the problem.

Also for Hotmail you should check out this: https://support.msn.com/eform.aspx?productKey=edfsjmrpp&...