When only a portion of your newsletter subscribers are sent the newsletter, do you receive any kind of message from Zen Cart? You might be running into a script timeout or your hosting company might be throttling your email sending (as a spam precaution).