I once worked with some reasonably large shared Web hosting companies and they frequently "oversold" on bandwidth, capacity, and the like - quite normal practice in the field.. and if people complained about slowness (perhaps their server was unlucky to have a handful of heavy users on it), they could be moved to quieter servers.

Seems like a similar thing is happening with GMail. The difference, though, is that most GMail users aren't paying a bean ;-)