You don't give any details about your Moodle site. Are you hosting this in house or with a third party? Are you using Linux or Microsoft Windows? Which version of Moodle do you have?
You say half of your users haven't got emails, did any of them receive emails automatically sent or did you manually send all of the successfully received ones?
If you've never been able to send emails from your site you'll need to find out if your server has the access to be able to send email. If not you will have to relay outgoing mail via a mail server (the SMTP Hosts setting). There are details on configuring this in the Moodle Docs.
If some of your users are receiving emails but not others and you're not using the SMTP Hosts setting then you may need an SPF record for your Moodle server so that recipient mail servers know you're not a spammer.
There's a Moodle eMail Test plugin which can help you troubleshoot sending mail in a controlled way.