I spent a few hours wading through something yesterday that I hope will save some other people some headaches.

I had the notifications module on, and it was sending notifications for node creations and updates just fine, but it seemingly wasn't sending anything when I commented on a node. It would TELL ME it did ("notification sent to x other users") but I would never get an email.

As it turns out (and this makes sense), if the person receiving the notification doesn't have permission to the item (i.e. the person is simply considered an "authenticated user" but that role does not have permission to "access comments") then the notice won't get sent, but you won't get notified in any meaningful way.