From what I know HotMail allows a maximum of 500 connections to its servers per IP. HotMail is somewhat difficult to contact, you (or, better, your web host) need to find a contact email from
http://postmaster.hotmail.com and email them. They should respond with a questionnaire about the server. After replying to their satisfaction, and if your server isn't sending WAY too much email, you should have fewer or no delivery problems.
It's also possible your host is having some temporary DNS troubles and cannot 'reach' the HotMail servers.
Yahoo has a similar questionnaire for non-shared servers to be exempted from the Bulk Mail folder. With AOL you can either phone their postmaster hotline to instantly remove a block on a server or URL and/or apply for a "Feedback Loop" which will tell you which users are complaining against your messages so you can remove them. An automated script to remove AOL complainers is available
here.
Regards