I'm having the exact same problem on my Nexus 6. The problem started roughly the time this thread was published, and I responded by uninstalling gmail to confirm gmail was the culprit. After the unintall I installed google inbox, and have been using that to monitor ONLY my gmail account for the last week. Today I turned gmail back on, ONLY for my gmail account, and I'm again having the exact same problem.
This is definitely a problem with the GMail app version 6.5, and since I'm only using the GMail account currently I can't see how it has anything to do with Exchange.