Depende de los filtros que aplique cada dominio, sobretodo los webmails, esto puede pasar.
Si la IP (o dominio) es nueva aún no tiene ninguna valoración sobre si es confiable o es spam, según el método de filtros usado por microsoft.
Si es en casos puntuales como en hotmail, no me preocuparía demasiado, puesto que no parece estar en una lista negra o base de datos como spammer.
Una manera de evitarlo es implantar SPF y/o el uso de DomainKeys.
Si quieres puedes consultar que dice microsoft de su servicio de correo
http://mail.live.com/mail/troubleshooting.aspx