So this is my issue: every time I open up Mail, there are messages sitting there that are days-old, even though I deleted those from my iPhone long time ago. (And I can confirm that those messages are gone seeing a nearly-empty inbox in Mail on OS X and in the iCloud web interface). I already tried disabling and enabling again the Mail toggle in the iCloud settings, but the issue persists. Same results when I tried disabling and enabling Push. I'm running iOS 7.1.2 in an iPad Air, and FWIW, I've been having this annoying problem since a long time ago.