I admin a few mail servers. I've run into trouble with Hotmail. Here's what I've learned:
First, there are a ton of url / domain blacklists available out there, no need to suspect a conspiracy within Hotmail and Yahoo. That said, I know they also maintain in house IP and domain based blacklists, along with full url blacklists. No idea if they share but I actually doubt it as that potentially weakens their competitiveness with the other email providers. Hotmail also uses a paid whitelist service too via an 'independent third party', although certain blacklist levels can even override that paid service.
Second, Hotmail splits mail up into three categories now, legit mail and spam which we're all familiar with, plus what they've dubbed 'graymail'. In short, graymail is legit opt-in mail that the user just never bothers to read. Thats right, your quadruple opt in email can be treated like spam by Hotmail if your users never bother to look at it. Generate too much, you're treated as a spammer. Can SPAM compliance or not, they don't care.
Third, if you manage to get on Hotmail's IP blacklist, there is no recourse that I can find. Their policy is tough expletive, move your mail server to a new IP or go away.
As far as the complaint level stats you can view through their Postmaster tools, they only show two of the three stats their system works on at the IP level, the complaint rate (people flagging mail, I *think* VIRI mail also counts in this column) and filter hits percentage, although this one is obfuscated to try and defeat spammers trying to tune around it. The missing stat is IP reputation, based on those first two stats over time along with external and internal RBL data. So when you DO setup on a new IP, it'll take awhile for their system to actually accept mail from you. You can subscribe to a feedback loop program, but that shows another issue with Hotmail:
They have no concept of traditional mail relays, they expect all individuals to be sending via Hotmail, Gmail, Yahoo, etc. All other port 25 traffic destined to them must be from commercial list serves. At least that's the impression I've gotten from going through all their postmaster policies and dealing with their ticket system. If you try to explain the idea of an ISP relay for use by people within that IP block, they just ignore it and resume pestering about opt-out notices, etc.