Seems like Google could easily treat it as a searching issue rather than a sorting issue, though. It would be easier than full text searching (which it already does).
At a certain point with data we have been living in a relative small sandbox in terms of data. As our lives spread to terrabytes of data and across many services, we to will be unable to run atomic operations on the whole of your data.
It is all in 1000 buckets. Ever gone beyond page 100 in google results? You can't. Even though there are millions of results you can only get to page 99 at 10 results per page because it too is built on GFS.
> Sorry, Google does not serve more than 1000 results for any query. (You asked for results starting from 1000.)
You can work around this issue by using the Advanced IMAP Settings and hiding the 'all mail' folder in IMAP, then setting the 'delete mail once all visible labels are removed' setting. I had issues with using this and offlineimap to sync... Sometimes when I moved a mail from one 'folder' to another offlineimap would delete it from one folder and then create it in another, but Gmail's IMAP server would see that the mail had no labels on it (in the middle of the operation) and then move it to the trash instead. This issue shouldn't come up with a client like Outlook or Thunderbird though because of the way that they operate (I believe that there is a 'move' command in the IMAP protocol that they use).