Are you sure about the re-uploading part? I've had an issue like that last week, and am currently stuck with my mails locally, not able to 'put them back' to the IMAP server. Not Gmail though.
[1]: https://superuser.com/questions/446135/import-e-mail-via-ima...