Vielleicht liegt's am mail header? Ist der anonym oder richtlinienkonform?
Hotmail is one of the biggest nightmares you can think of. They provide a form to unblock your IPv4 address and also to apply for their anti spam programs, but this won't help if you have a small mail server with < 100 mail a day. Believe me, I tried.