I have a free Google Apps account with ~2GB of mail. I definitely saw the same symptoms for quite a while, which eventually got to the point of serious downtim

I have a free Google Apps account with ~2GB of mail. I definitely saw the same symptoms for quite a while, which eventually got to the point of serious downtime last year. At some point, the last big downtime (over a day!) involved some sort of transfer to different infrastructure (and I wish I could remember the exact wording now), and since then it's been back to lightning fast. There definitely seem to be some endemic issues, but they're only for certain slices of users, it seems.