I ran into this a while back, the notification is only sent to moderators, and admins are not necessarily moderators. To get the notifications sent to everyone, click “grant moderation” for all of your admins.
We actually find this quite useful, because we have technical administrators that we do not want to be bothered by these notifications. But maybe this is actually a bug @codinghorror?
@bas, the other condition you might be hitting is that the notification will not be sent to anyone that already has an unseen pending_users notification.