I got the same issue with my emails company... you have to wait some time(some weeks...) to get your emails working ok...
Did you define correctly your PTR (reverse DNS)?
Did you check DNSBL with mxtoolbox, maybe you are blacklisted in some servers? if it's your case you have to request blacklist remove in the RBL where you have been listed.
The most hardest one is to get your emails working on hotmail (more hardest than gmail).