Got my Gmail inbox down to *50* today because I am so awesome. I found out it's not that hard. You just leave stuff in there for about 6 months. Then you go through and delete about a third. Last, archive about two-thirds, about half of those with your 'maybe' tag. Voila!
Parts of my Gmail account that are not so awesome: 49 Drafts that I really should cull down and 15650 Spam :-(