I decided to use the Uploader for Mac to backfill old emails and I let it run overnight. I used the option to "assign additional label" during the upload to mark everything with UPLOADED 18-AUG-2012.
The upload was successful (me=email hoarder, uploaded 10k+ files). Today, I added my email account (gmail config) to my iPhone. When I load up the label view, it loads a set of the oldest emails (2007) instead of more recent emails. I too had emails labeled with numbers 1-9, and when viewing emails in those labels the same sort issues happen - older first, skipping over more recent.
I'm not sure if this is an iPhone issue, quality of data from my host provider, weird timestamps assigned by the uploader, or something else. Thoughts and advice are appreciated.