I have heavy issues with HOTMAIL since they reject ANY legitim messages as SPAM without any reason. All of my 50 Servers are worldwide and in different subnets. It is nearly impossible that all 50 Servers have spamed HOTMAIL, since my servers accept only authenticated SMTP from clients.
Not "nearly impossible." I work daily with people who run servers exactly like that, yet spam of all sorts is spewing from their mail queues. Most of the ones I see are SMTP accounts with weak passwords. The spammers authenticate as the users and bam, the server is a spam source.
With Hotmail, make sure that you have a reverse DNS record for your server's sending IP, that the A record for that name resolves to the same IP, and that your SMTP banner greeting lists the same name. Also, if you use SPF records, do not use the PTR option - they reject mail from domains that contain that option.
