CiviMail is only sending to half the recipients
Some pointers on how to debug this a bit further. Links are to the CiviCRM demo site - visit http://dmaster.demo.civicrm.org/ and log in. (WordPress / Joomla URLs will differ.)

Check output of "Send Scheduled Mailings" scheduled task.


http://dmaster.demo.civicrm.org/civicrm/admin/job?reset=1


This is the task which delivers CiviMail messages. It's executed from cron regularly, and there's a log visible at the URL above ("View job log" for "Send scheduled mailings"). Check if there's any output there. (If there are no job log messages, it's not getting executed!)

Check your cron setup


https://docs.civicrm.org/sysadmin/en/latest/setup/civimail/#setting-up-the-cron-job


CiviCRM and CiviMail depend on cron - scheduled jobs triggered by the system. A single CiviMail may take several cron runs to deliver all the emails. This task should be executed by the system somehow. The task will be run in the console and may generate output (success or failure). It should be executed as the webserver user for filesystem permissions, and ideally set up to capture output so you can investigate if it's not working as expected.

Investigate your mailserver logs

Use tail / grep etc to observe the mailserver logs and see which addresses get messages queued for them. It sounds like you've already established that the missing messages never get there, but worth including in this list.

Get support


Professional support
Community support via chat
You can link to your question here to save explaining over!