[JamesBrooks]

We've had this problem a lot, even with specific in house policies for how mail should be sent from our web applications. I've found that making sure the SPF record is correct and very 'tight' helps a lot. Also make sure before you're mail server isn't running as an open relay well before you send a test e-mail to Hotmail (make sure everything is perfect before you send to hotmail).

After that, don't just start sending a large bulk of e-mail to hotmail, send a few (they'll run some tests, open port, check SPF, etc!!). After a bit then start shipping mail out to hotmail.

Even after all of this you can still be up the creak, we've gone to using AuthSMTP at work now (having Postfix directly proxy the requests on). It's fast and we can deliver to hotmail (a lot less stuffing around).