I've often read about how email was broken. Maybe it's because I only receive about 10 mails per day or because GMail's interface with some plugins suits me well, but I'm actually very happy with it. But when Google forced me to switch to their latest interface, my labels' colors became a bit messed up and I decided to use the opportunity to reorganize my inbox flow.

I set up a simple rule to follow:

Every incoming mail must hold one of the predefined labels.

The first part of this rule states that each mail should hold one label, and only one. It's the least organization an inbox should provide, without cluttering it too much.

The second part enforces a fixed number of labels in order to avoid creating ones on the fly for each new mail. You can still create new ones, but not without making sure it'll be heavily used in the future. Here's my list:

GMail labels organization

Apart from the Notes label (which synchronizes with iOS' Notes app), the 7 other labels, along with sub-labels, should be able to organize every incoming email.

2do

The 2do label is a meta one. I use it to tag mails that are currently important and require further actions. I use the GMail 'Multiple Inboxes' feature to have a second inbox above the regular one, filtered with only 2do mails. These are for example mails I need to respond to, a shipping process to keep track off, a due payment...

Using keyboard shortcuts, it only takes a few strokes to make a mail show up in that special inbox: j/k-o-l-2 and 'Enter'.

Admin

Admin label

This one is for administration stuff: bank, health insurance, taxes, (un)employment processes, various subscriptions... Actually, there is a sub-label called Inscription (Subscription) with which I tag every new membership mail, the ones where they send you a welcome message along with your login information (and sometimes even with your password in plain text...). Anyway, it helps me keeping track of any service, real or online, to which I've subscribed. Sometimes, I wonder "What was that website I've subscribed to again?" or "What's my login again?", and this sub-label helps me answering these questions.

E-commerce

E-commerce label

This label is for anything shopping-related. The 3 most important sub-labels here are:

The Apple and Voyages (Trips) sub-labels are more specific: iOS purchases and trip reservations.

Contact & Friends

These two go along as they work pretty much the same way. The way I use them depends on the sender's identity:

Newsletter & Notifications

These labels are used for mails sent from companies.

To me only (private) To me among others (public)
From a company Notification Newsletter

Newsletters are just what they are: informations mails to which I have subscribed and are sent to many people.

Notifications label

Notifications are everything else sent by a company. It's usually just a small mail telling me that I have received a private message, or that a credit card or domain is about to expire, or that someone responded to one of my comments.

I keep seperate sub-labels for notifications from Dribbble, Facebook, Twitter...

Reminder

Reminder label

I have 2 kinds of reminders:

Wrap-up

With this setup, and with the use of GMail filters, every email in my inbox holds a single label (except when I also add the 2do label but it's just temporary).

GMail Organized Inbox

For the several months during which I have used this organization, I haven't felt the need to create new labels, nor to think too long about which one to apply. And I don't know how it would scale up with much more mails to deal with, but I don't think it'd be too difficult to handle.