We are going to have to look around the periphery of this one. Admin notification and user subscription emails are sent at the same time, using the same basic code structure and both using the email address that WP holds for that user. The only differences are the email content and the subject line. If one goes there should really by no reason for the other not to go. And – worth noting – when we have reports of emails not being sent this is across the board – not just one type.
So – something odd is clearly going on.
The obvious first one would be spam filters… make sure these are not being dumped as spam.
Also – when logged in as an SP admin, open up your SP profile and check your permissions on some of your forums. As an admin you should have all permissions turned on except two. Is this the case?