Innanzitutto potresti ritardare l'invio con un utilizzo a blocchi delle email. Poi procedi con una pausa tra un blocco e l'altro (anche un refresh della pagina in javascript andrebbe bene).

Naturalmente ogni blocco devi flaggarlo come "inviato" prima del refresh, altrimenti ti invia sempre le stesse email.

Se il problema non dovesse risolversi, dovresti optare per un servizio SMTP a pagamento che ti permette di utilizzarlo all'interno del tuo codice PHP.

Es.

Prima del refresh

codice:
 SELECT name, email FROM users WHERE inviato=0 LIMIT 0, 30
Durante il while:
codice:
 UPDATE users SET inviato=1 WHERE id=$id
Poi fai eseguire il refresh (es.. 20 secondi)