I have 50,689 messages now, down from ~68K. So I deleted like 18K. Again, it seems ridiculous that I need to delete messages.

However, it is even more ridiculous that if this is the solution that works, Gmail makes it really hard to make it work. There is no way to search for the biggest messages. There is no way to isolate all mailing lists. I can't find a way to search for [ in the subject.

I ended up launching up etacts and otherinbox and looking for people I used to contact years ago (old projects) and deleted emails from those projects.