This is frequently the cause of this problem.
Your mail is being saved on your server rather than being deleted as you download.
They will probably delete mail over, say, 30 days old, which is why you sometimes can and sometimes not.
How to change this setting. I can't remember, so you'll have to dig around a bit, or wait until someone comes up with the answer.