Sorry to hear your issues with sending emails out but common issues / reasons is
1) Your SMTP isn't setup properly with the Reverse DNS Entries etc.. and you should have the admins check for you with your host.
2) Chances are the IPs are not blacklisted but just flagged, and you + your host should assist you in contacting hotmail/yahoo to get this resolved, typically takes one week for them to respond from our experience.
After everything works ok, you need to make sure your DEDICATED IP Address is clean and not sent out any spam from it. Aside from that, your host must monitor their IP Blocks carefully to make sure other users on the same ip block are clean and not spamming.
__________________ââ¢ CirtexHosting â¢ Providing Affordable and Quality Web Hosting