Oh, yeah 2 more things ... recently had this happen ... there is a setting in Moodle for the address to use with 'noreply' when messages are distributed. Is that a valid EMail address - valid domain?
And, when one post something to a forum to which users are subscribed run the cron job a few times via browser - until the distribution of messages kicks in. That output (of cron) sometimes gives hints as to issues. Also, after doing so, check your server's mailque. Could be there is a cap/choke and only 50 such messages can be sent at one time ... the others get stuck in the que for later attempts at delivery by whatever is setup on your server. That's a provider policy with some VPS systems.
'spirit of sharing', Ken