Are the mail logs saying anything about what is going on? Ie, refusing mail from hotmail... Are the emails from hotmail being returned to the hotmail account? What are those emails saying is the reason the mail was bounced?
Are you running with the acccess.db file? If so is there anything in there denying hotmail? Also, check your sendmail.cf file for any hotmail references and if there are any in there comment them out and see what happens.
The very first thing I would do is take a look in the mail logs and send an email from hotmail myself and see what happens to the email and how it gets returned.
Hope this helps,
Paul
