How would you decrease the amount of storage needed for storing e-mail messages for Gmail?  

@Hung Nguyen : Great answers. good structure of thinking. 

You touched upon rgiht points. You brough in the case large number of media files as a problem. 
Its indeed a real problem and one of the biggest reason. 

While proposing the solution for the same problem, you proposed handling overlapping/duplicate media.  I think there could be more solutions for media files. 

I solved this problem in real-life. I wrote the prototype code back in 2014 and it was shipped in production. My outlook inbox was getting full and it was because I have no control over the incoming emails. People were sending big docuements attachment. 

I wrote a outlook pluing using visual studio. It would save all the attachment of e-mail into my local computer's folder. That folder is syncing using cloud storage. I created one folder for each sender. under each sender I created sub folders for each email thread sub folder name was  subject of email. 

After saving the attachment to that folder I was able to remove the attachment from e-mail and add the hard coded path of c:\users\<mayname>\<my-cloud-storage>\E-mail attachments\ <Sender-Name>

Above my version 1 PoC. 

My Company made CloudStorage called.  I learnt about how to use their API to programmatically upload the file and I made version 2, which directly uplaods to cloud storage. 

Was problem completely solved? No. While I am seding e-mails with attachment, that's also consuming space, as its stored in my sent folder.  Also recepeint's inbox is getting full due to my email. Imagine there can be more than one recepeint. 

I created version 3 of my PoC that would strip the attachment of all my outgoing email and uplaod it to cloud storage and just place the link in email.  

I still have those attachment folders and they weight more than 35 GB ( trash of over 6 years). 
Our CloudStorage product, shipped this feature in form of Outlook plugin the very same year. 

I pitched this idea to head of product alogn with my PoC and he said If people's data is living in out cloud storage they are less likely to churn. 

Later in 2017 on wards we saw Microsoft outlook started doing the same,  while you are sending a document over email, it gives an option want to attach as link or attach the original document. 

So this was my real life story. 

I would pictch creating connectors like the one I mentioned above.  I should be able to polugin my Dropbox account or Google Drive account.