Push notifications wont via Exchange (Gmail & Outlook)

Hey,

I've been using Gmail (via Exchange Sync) since quite some time now. Just recently, I noticed that I wasn't being notified instantly for all my emails received at Gmail or at the new Outlook.com offered by MS.

I've tried rebooting, removing iCloud and all other accounts and just adding a singe MS Exchange Account for Gmail. Still no go.

Any help ? It's really annoying.

Thanks!