Many internet providers are blocking the use of PHP Mail (SendMail). Instead of deleting the emails, they move them into the spam folders of clients. Unfortunately, this means that the client may never see their invoice.
If you change your settings and configure for SMTP by going to Setup -> Settings -> Email, it will fix this issue about 99% of the time.
You should also ask your clients to whitelist your company emails.