Recently I had to upgrade my Gmail account for additional storage. I was nearing the 8 free gigs of data they give you and didn’t want to keep seeing the big red “Buy more storage!”. I bought the $5/year 20 gig plan. A few weeks later I noticed that my Gmail was now reporting i was already using ~18 gigs of my total 30 gigs of data. I couldn’t believe it, how did I manage to more than double my used Gmail space within 2 weeks? I had used Gmail for 8 years to get to 7 gigs of data.
After looking around there didn’t seem to be anyone who could report the problem, nevertheless have a fix. I then tried to empty my Trash, which at the time said ~200 messages. As soon as I emptied it my used space dropped to 7.3 gigs, which is what I expected.
Long story short, it would appear that Gmail has a bug in reporting the number of actual messages in the trash, or doesn’t truly ’empty’ it unless click it. If you think you are using much less space than it is reporting, try emptying your trash manually. It worked for me and a number of other guys in the company.