Steven Schofield noticed a strange Gmail bug: attachments use more storage than they should.
For example, one of my Gmail accounts used 1567 MB of storage. I composed a new message, attached a file that had about 8.42 MB and saved it as a draft. Gmail's footer message was: "You are currently using 1590 MB (21%) of your 7479 MB." Gmail used 3 times more storage for my message and MIME encoding couldn't add so much overhead. I discarded the message and Gmail informed me I was using 1579 MB. After composing a message and deleting it, I lost about 12 MB.
I composed another message, attached the same file and sent it to an email address. Gmail used 23 MB to send a file that only had 8.42 MB. After deleting the message, I lost once again 12 MB of storage.
The most likely explanation is that Gmail's Flash uploader creates hidden messages for each file you upload. When Gmail launched the Flash uploader, these temporary messages were sent to the trash. Now they're probably no longer displayed.
Update (a day later): it's fixed. Google now shows the temporary messages from the trash.