I don't know whether this helps at all, but...
Sometimes, when a bona fide domain gets abused for spamming purposes, it gets temporarily blacklisted (some blacklisters are rather zealous in their efforts) until the domain owner either fixes the technical vulnerability that made the abuse possible or kicks off the offending user, whichever may be the case. Either way, the domain in question is temporarily blacklisted.
This never happened to me with my own domain, but it did happen to me once with dropzone.com, which is (among other things) a free e-mail service for skydivers. When I reported that my mails to CM were being rejected, it was pointed out to me that occasionally they temporarily find themselves blacklisted due to an exploited security breach or a mala fide user. I would imagine this might happen to Hotmail, Yahoo and others from time to time as well, so perhaps either Hotmail entirely or at least one or some of their outgoing servers were temporarily blacklisted due to accidental abuse by spammers.
Again: this might not be the case here at all, but I figured I'd mention it anyway.