I've seen some speculation that Gmail slows down because your account is assigned to a server with other older accounts which are also growing and straining server capacity. Is it possible that the speed increase comes from being assigned to a new server more than the decrease in mailbox size? It would interesting to see someone test this by fully restoring their old account in a new account and comparing performance.