You will need to start by figuring out where it goes wrong. Are the mails actually sent from your server? Are they maybe catched by a Spam filter at the client side? Etc..
Start by running Email Diagnostics under: AdminCP -> Maintenance -> Diagnostics.
Some good reading (thanks Alfa1 for the link in your sig):
Hotmail, Gmail, Yahoo & AOL's guidelines for bulk mailing need your attention.