That reference says "slowness is really only an issue for power users of the service — those with hundreds of thousands or even millions of messages."
I only have 50K messages at a little over 4GB. People are saying they have inboxes as full as mine and are still fast.
Something doesn't add up. Is my account on an old infrastructure?