As suggested on reddit, they all might belong to the same spammer. I don't know about hotmail account creation, but if it's protected by captchas only spammers have no problems making the accounts. Some captchas can be decoded in code with high success relatively quickly, others can be fed to mturk style services.
Google has phone verification now, I guess that's harder to overcome.
You can (or could) buy 'aged' hotmail address for cents - these have never been used by real users. As for captchas a quick google search will offer up a heap of solving services, many even with APIs! The only way to protect a service against spammers or blackhatters is to stop it from being useful to them in the first place (i.e. don't allow links in profiles, etc. Harder for services like email which can't really be hobbled to prevent this sort of use without trashing the key function).
Either through automation software or (as you note) mturk style services, pretty much any anti-spam defence can be breached.
Presumably if the list of hotmail accounts was just for outbound spamming then one of the addresses on the list would have been used to send the original phishing email.
Google has phone verification now, I guess that's harder to overcome.