For me, the watch is as dependable as the phone is. I don't know why, but my phone will sometimes not show new emails. Sometimes it's just a delay and sometimes they won't show at all until I open the email app. So I might not always get notified of new mails, but that's because they didn't show up on the phone. Remember, your watch can't get anything that doesn't show up on the phone.
Your mail service most likely does not support a Push system and instead is relying on you either manually downloading your emails or creating a faux-push system where it calls for emails to be downloaded at certain intervals.
The push service is dependent on whether or not the email service you are communicating with can support that function.
Yes, I'm not sure. Some of them are probably gmail messages, which apparently no longer support push. But my main email is Mac.com/Me.com and I've also had that happen with it. For example, I might be out of the house and the moment I come back home and into range of my home wifi I will get some messages. And yes, I have cellular data on. I find that restarting the phone seems to help.
When you walk out of range then back in, does your Watch show you the notifications you missed?