Das PHP Skript, welches die Mails versendet, übergibt die Mail nur via Aufruf der Funktion mail() an irgendein Programm (welches genau, ist in der Konfiguration festgelegt, meist sendmail) und erwartet von diesem die Bestätigung: "Mail angenommen".
Insofern ist der Fehler sehr wahrscheinlich beim Programm zu suchen, welches die Mails versendet.
Auf einem Webspace kann sich sowas natürlich schwierig gestalten, da die Zugriffsmöglichkeiten beschränkt sind, vermutlich kannst du nicht einmal die Logs des Mailservers einsehen?
Hoster fragen wäre eine Möglichkeit, bei 1.000 Mails auf einmal wird der aber wohl auch sagen, dass du ein größeres Paket nehmen sollst
Evtl. passt du den Mailversand so an, dass die Mails nur in kleinen Paketen verschickt werden, also bspw. alle 5 Minuten 50 Mails.