Hola,
La funcion mail() devuelve false si hubo algun error al pasar el mensaje al servidor SMTP saliente o a sendmail (Depende de la configuracion). Eso es lo primero que deberias comprobar.
Luego tampoco dices si envias los emails de uno en uno o dentro de un bucle (dices que es un newsletter). Hay hostings que limitan el numero de emails por hora que puedes enviar. Asi qeu si te pasas del numero deja de enviar.
Tambien podrias mirar en
www.dnsstuff.com si tu IP o tu dominio estan en alguna lista de spammers. Supongo que no, pero por mirar no pasa nada.
Y luego hay miles de razones mas por las que un email puede no llegar a su destino.
Suerte.