I was having the exact same problem when my account was using around 85% of the allowed storage.

I also had another account with very little emails stored and it was pretty fast.

My solution (quite lame): I redirected the "full" account to the other one and started to only use the later. So far no more problems...