I've got most of my groups set up to require group admin approval. However, I seem to ever get 2 email "Group name - New User!" requests when users start making join requests, and then go to the back end and find 5-15 there waiting for me.
Are you getting an actual email direct from GJ or are you getting a new private message notification from UddeIM regarding the PM? GJ by default sends PMS or Email. If PMS fails it'll send Email. If set to Email Only within GJ > Config > Notifications then it'll always only send an email.
It's possible you're hitting email limits from your web host. Contact them and see if email limits are being sent and if not to check the outbound emails to see if they're all sending or not. Some hosts don't allow offsite From Address and From Name so you may need to set these within GJ > Config > Notification to force all notifications to come from your site otherwise they'll send from the user trying to join the group.
On a sidenote, I'm also a little confused about the CB notifications module which I've installed -- it appears to only be for CB and doesn't tell a group owner (in front end) that they have pending group join requests (at least not that I've seen so far). So I need to install/do something there?
Doesn't integrate with GJ. If you need a module for this then install the GJ module included with the GJ package and set its mode to "Approval".