Posting incase any IMAP/SMTP buffs follow me:

Gmail copies whatever is sent via SMTP into IMAP. If you try to APPEND the same message to Sent, you get a dupe.

If you APPEND to All Mail though, then immediately store a \Sent label, it doesn't duplicate…90% of the time.

So why does this work most of the time, but sometimes fail?

When it's working the server seems to return both EXPUNGE and EXISTS simultaneously. If it fails, you only get an EXISTS.