Kolla om ni har ett SPF värde inlagd i Era DNS zoner för domännamnet som skickas ut dessa mail.
Ett annat tips är att skicka ut standard "text" baserade mail utan länkar, Hotmail är väldigt känsliga när det gäller länkar.
Samt du kan väl kolla följande angående SenderID:
http://www.openspf.org/FAQ/Hotmail_and_SPF