Sounds strange to me, too.
I've had a similar problem several times, with my stuff and with a couple of friends. The fix that worked was to remove the offending e-mail account altogether from the misbehaving device, shut it down, restart it, and reinstall.
That's been needed quite a few times with iPhones and iPads, and a couple of times with laptops.
No, I don't have a clue what removing and adding back does, other than that it worked.