Can you resume sending mails to a list of which only part of the addresses are having had a newsletter?
To avoid automated spam testing, most hosting companies avoid reporting back on failed sending. If you somehow know who got and email and who didn't, you could suspend or remove subscription for those who did, send email again and after that re-enable users. That's pretty universal method, works for any mass sending mechanism.

If you don't know who got your email and who didn't, only raw number, you have a problem that's unsolvable.

For the future, Drupal integrates pretty well with some paid mail sending services. That's a solution for sending large amount of mail and keeping page on shared hosting. If you want to avoid mail sending services, virtual private server shouldn't have a limit on sent mail count. Sending mails is pretty expensive in terms of cpu and memory, and it's an outdated technology, so it's only to be expected shared hostings will limit and discourage it, except for small quantities like registration confirmation etc.