Hola,
Cuando no se configura una cuenta de envío de correo smtp, Moodle intenta el envío mediante PHP y, últimamente, debido a las restricciones de los correos entrantes de los usuarios, éstos son rechazados.
Sin embargo, cuando se configura un servidor SMTP para el envío de los mensajes, es éste servidor el que los envía, por tanto si no lo hace, y están los datos bien configurados, será por algún tipo de restricción de dicho servidor de correo saliente SMTP por lo que no se lleva a cabo el envío al total de los usuarios.
De todas formas, esperar a que un servidor de correo saliente envíe 5000 mensajes a destinatarios distintos sin que se imagine que puede ser spam, es esperar demasiado...
Yo, revisaría las restricciones de dicho servidor de correo saliente y/o preguntaría a su soporte.
Un saludo.
JP