Are the emails going into folders, or just the inbox?
It's odd, because normally you should just have to enable notifications and make sure that Sync is on for your email accounts.
Also, if you have a "task Killer" app, uninstall that. It could be causing issues with notifications.
Here is what happened to one guy. Maybe you need to read all the emails or clear our the ones that aren't read...
I finally figured out what's going on. Normally I have several email messages in my inbox. When new mail arrives it gets added to the top and at the same time my Nexus gets an alert. Yesterday I happened to process all of my outstanding email and clear out my inbox. When new email arrived to my empty inbox, the Outlook running on my PC immediately read the email and marked it as read (even though I might not have actually read it personally yet - it's how I like Outlook set up). When the email gets marked as read immediately after the message arrives, no alert is generated on my Nexus. Because I was not reading my gmail account with Outlook it always worked, but email to my Exchange account was failing once I emptied my inbox. It just happened to be a quiet few days at work and I haven't been getting much email.
It's the first time in a long time that my inbox has been empty, so the problem just didn't get a chance to occur. Now that I know what's happening I may change my Outlook settings to to mark as email as read until I tell it to.
Identical problem, but not sure about the given solution. What did the trick for me was altering the account (Exchange Active Sync) "Sync schedule" to Push from Manual. I'd switched it previously to Manual as Push appeared to be draining the battery. Resetting the schedule to Push definitely solved the notification problem. So it's a tricky choice, either have notifications and lose battery power or delay notifications and conserve power. I've set the sync currently to 5 minutes and will see how that works.